国外h5分享网站,曲靖做网站的公司,有没有做网站源代码修改的,交通运输行业网站建设难度#xff1a; 中等通过率#xff1a; 53.9%题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述 给定一个二叉树#xff0c;返回它的中序 遍历。
示例:
输入: [1,null,2,3]1\2/3输出: [1,3,2]
进阶: 递归算法很简单…难度 中等通过率 53.9%题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述 给定一个二叉树返回它的中序 遍历。
示例:
输入: [1,null,2,3]1\2/3输出: [1,3,2]
进阶: 递归算法很简单你可以通过迭代算法完成吗
解法
中序变量即按照 左-中-右 的次序来对二叉树进行遍历。对树进行遍历使用递归会非常简单。当然不使用递归能够带来性能上的提升。
递归解法
class Solution {public:vectorint inorderTraversal(TreeNode* root){vectorint res;traversal(root, res);return res;}void traversal(TreeNode *node, vectorint res) {if (!node){return;}traversal(node-left, res);res.push_back(node-val);traversal(node-right, res);}
};基于栈的解法
中序遍历先访问左孩子因此第一个访问的节点需要深入到叶子节点上在递归解法中中间节点都保存在调用栈上在迭代解法中需要使用一个栈来保存中间节点。
从根节点出发把节点压入栈中然后进入左孩子再入栈。直到所有的左孩子都入栈了。然后弹出一个节点访问该节点。进入其右子树然后回到上一步。
你仔细观察基于栈的方法本质是使用一个栈来模拟调用栈。因为 traversal(node-left, res) 会进行新的调用栈但是其后还需要访问 node-val 和 node-right因此在进入 node-left 之前把 node 保存在栈上。
代码 2 的内层循环完成的就是 traversal(node-left, res) 。node node-right 复用了前面的 while 循环实现了 traversal(node-right, res)。
代码 1
void traversal(TreeNode *node, vectorint res) {if (!node){return;}traversal(node-left, res);res.push_back(node-val);traversal(node-right, res);
}代码 2
class Solution {
public:vectorint inorderTraversal(TreeNode *root) {vectorint res;stackTreeNode* stk;TreeNode* node root;while(node || !stk.empty()){while(node){stk.push(node);node node-left;}node stk.top();stk.pop();res.push_back(node-val);node node-right;}return res;}
};
