域名注册网站建设方案,营销网站制作教程,宝安建网站的公司,城镇建设部网站二叉树的理论基础#xff1a;#xff08;二叉树的种类#xff0c;存储方式#xff0c;遍历方式 以及二叉树的定义#xff09; https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
二叉树的递归遍历
Leetcode对应的三道习…二叉树的理论基础二叉树的种类存储方式遍历方式 以及二叉树的定义 https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
二叉树的递归遍历
Leetcode对应的三道习题 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 这个的话还是比较容易的。就是依次按照他的访问顺序进行递归遍历即可。
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayListInteger();preorder(root, result);return result;}public void preorder(TreeNode root, ListInteger result) {if (root null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();inorder(root, res);return res;}void inorder(TreeNode root, ListInteger list) {if (root null) {return;}inorder(root.left, list);list.add(root.val); // 注意这一句inorder(root.right, list);}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();postorder(root, res);return res;}void postorder(TreeNode root, ListInteger list) {if (root null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意这一句}
}二叉树的迭代遍历非递归
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。
1.前序遍历迭代法
前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。因为这样出栈的时候才是中左右的顺序。
// 前序遍历顺序中-左-右入栈顺序中-右-左
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null){return result;}StackTreeNode stack new Stack();stack.push(root);while (!stack.isEmpty()){TreeNode node stack.pop();result.add(node.val);if (node.right ! null){stack.push(node.right);}if (node.left ! null){stack.push(node.left);}}return result;}
}2.后序遍历迭代法
先序遍历是中左右后续遍历是左右中那么我们只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中了如下图
// 后序遍历顺序 左-右-中 入栈顺序中-左-右 出栈顺序中-右-左 最后翻转结果
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null){return result;}StackTreeNode stack new Stack();stack.push(root);while (!stack.isEmpty()){TreeNode node stack.pop();result.add(node.val);if (node.left ! null){stack.push(node.left);}if (node.right ! null){stack.push(node.right);}}Collections.reverse(result);return result;}
}3.中序遍历迭代法
刚刚写的前序遍历的代码不能和中序遍历通用因为前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。
那么再看看中序遍历中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。
// 中序遍历顺序: 左-中-右 入栈顺序 左-右
// 需要定义一个指针用于遍历二叉树
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger result new ArrayList();if (root null){return result;}StackTreeNode stack new Stack();TreeNode cur root;while (cur ! null || !stack.isEmpty()){// 一路向左直到左孩子为空if (cur ! null){stack.push(cur);cur cur.left;}else{// 此时为空就把当前栈里的节点给弹出// 栈顶的元素就是我们最近访问过的元素cur stack.pop();result.add(cur.val);// 遍历右孩子如果右孩子依旧为空的话就回到else里把当前节点给弹出cur cur.right;}}return result;}
}
