做网站有哪些,易语言 做网站mysql,可以直接打开网站的方法,国外做装饰画的网站题目
94. 二叉树的中序遍历 - 力扣#xff08;LeetCode#xff09;
什么是中序遍历
二叉树的中序遍历是按照左-根-右的顺序访问二叉树中的所有节点。
具体过程#xff1a;
先遍历左子树#xff08;递归#xff09;然后访问根节点最后遍历右子树#xff…题目
94. 二叉树的中序遍历 - 力扣LeetCode
什么是中序遍历
二叉树的中序遍历是按照左-根-右的顺序访问二叉树中的所有节点。
具体过程
先遍历左子树递归然后访问根节点最后遍历右子树递归
例如对于下面的二叉树 1/ \2 3/ \ \
4 5 6
中序遍历的结果是[4, 2, 5, 1, 3, 6]
遍历步骤
从根节点开始先访问左子树访问节点4左叶子访问节点24的父节点访问节点52的右子节点访问节点1根节点访问节点3右子节点访问节点63的右子节点
递归写法
读者可能会出现的错误写法
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result; dfs(root,result);return result;}void dfs(TreeNode* root,vectorint result){if(!root){return;}dfs(root-left,result);result.push_back(root-val);dfs(root-right,result);}
};
在dfs函数中result参数是按值传递的而不是按引用传递的这会导致对result的修改不会保存。
每次调用dfs函数时
会创建result的一个新副本当执行result.push_back(root-val)时只是向这个副本中添加元素递归调用子节点的dfs时又会创建新的副本当函数返回时这个副本被销毁其中存储的所有节点值都消失了
正确写法
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result; dfs(root,result);return result;}void dfs(TreeNode* root,vectorint result){if(!root){return;}dfs(root-left,result);result.push_back(root-val);dfs(root-right,result);}
};
非递归写法
思路
沿着左子树一直深入将所有节点压入栈中
当无法继续向左时弹出栈顶节点访问它
然后处理该节点的右子树
具体实现步骤
创建一个空栈和一个指向当前节点的指针curr初始为根节点
当curr不为空或栈不为空时循环
如果curr不为空将curr压入栈然后curr移动到其左子节点
如果curr为空弹出栈顶节点将其值加入结果数组然后curr移动到其右子节点
读者可能的错误写法
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode*st;TreeNode* node root;while(node || !st.empty()){while(node){st.push(node);nodenode-left;}//将栈顶的元素放入数组中result.push_back(node-val);st.pop();node node-right;}return result;}
};
在尝试访问node-val之前node已经是nullptr。在内层while循环结束后node已经是nullptr因为循环的终止条件就是node为空。因此在这之后直接访问node-val和node-right会导致空指针解引用错误。
正确的方法
vectorint inorderTraversal(TreeNode* root)
{vectorint result;stackTreeNode* st;TreeNode* node root;while(node || !st.empty()){while(node){st.push(node);node node-left;}node st.top(); // 先获取栈顶节点st.pop();result.push_back(node-val);node node-right;}return result;
}
