织梦网站程序5.7首页模板,百度打网站名称就显示 如何做,网站开发需求文档怎么写,专业的餐饮网站建设仅为个人记录复盘学习历程#xff0c;解题思路来自代码随想录
代码随想录刷题笔记总结网址:代码随想录
二叉树的迭代遍历(不使用递归实现遍历)
递归的实现就是#xff1a;每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中#xff0c;递归是通过栈实现…仅为个人记录复盘学习历程解题思路来自代码随想录
代码随想录刷题笔记总结网址:代码随想录
二叉树的迭代遍历(不使用递归实现遍历)
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中递归是通过栈实现的自然也可以直接通过栈实现对二叉树的遍历。
144.二叉树的前序遍历
二叉树在树中前序遍历是中左右使用迭代遍历每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。要先加入 右孩子再加入左孩子是因为基于栈先进后出的特性这样出栈的时候才是中左右的顺序。中间节点出栈才压入左右节点
使用迭代法的前序遍历代码示例:
public ListInteger preorderTraversal(TreeNode root) {//初始化栈列表根入栈ListIntegerresnew ArrayList();StackTreeNodestacknew Stack();//根为空if(rootnull)return res;//根不为空stack.push(root);while(!stack.isEmpty()){TreeNode nodestack.pop();res.add(node.val);if(node.right!null)stack.push(node.right);if(node.left!null)stack.push(node.left);}return res;}
94.二叉树的中序遍历
二叉树的中序遍历是左中右二叉树的中序遍历不能像二叉树的前序遍历和后序遍历一样因为二叉树的中序遍历的访问顺序对节点的遍历和处理顺序将节点值加入到结果数组中不相同所以需要使用其他方法。使用一个指针来控制访问和处理。对于每个树子树的根结点先不断向左访问将路径上的元素压入栈中直到到达null再开始处理将null的上一个访问的节点数据存入结果数组将指针指向该结点的右节点。
使用迭代法实现的中序遍历示例
public ListInteger inorderTraversal(TreeNode root) {ListIntegerresnew ArrayList();if(rootnull)return res;StackTreeNodestacknew Stack();TreeNode curroot;while(cur!null||!stack.isEmpty()){if(cur!null){stack.push(cur);curcur.left;}else{curstack.pop();res.add(cur.val);curcur.right;}}return res;}
145.二叉树的后序遍历
二叉树的后序遍历是左右中二叉树在树中前序遍历是中左右在使用迭代遍历时只需要基于前序遍历将左右节点的顺序交换然后再将结果数组反转就可以了。
使用迭代法的后续遍历示例
public ListInteger postorderTraversal(TreeNode root) {ListIntegerresnew ArrayList();if(rootnull)return res;StackTreeNodestacknew Stack();stack.push(root);while(!stack.isEmpty()){TreeNode nodestack.pop();res.add(node.val); if(node.left!null) stack.push(node.left);if(node.right!null) stack.push(node.right);}Collections.reverse(res);return res;}
