谈谈你对二叉树递归遍历算法及其应用的理解,二叉树遍历递归和非递归的区别 知乎
00-1010前言1。递归遍历2。非迭代遍历3。二叉树的统一迭代法
00-1010二叉树的遍历方法分为前序遍历、中序遍历、跟序遍历和顺序遍历。
00-1010对于递归，我们不得不说递归有三个要素：以前导遍历为例。
递归参数和返回值
因为您想要打印出序言中遍历的节点的值，所以您需要在参数中传递列表中放置的节点的值。另外，不需要处理任何数据，也不需要有返回值，所以递归函数的返回类型是void，代码如下：
public preorder (treenode root，list integer result)确定终止条件。
在递归的过程中，怎样才算是递归的结束？当然，如果当前遍历的节点是空的，那么这一层的递归就结束了，所以如果当前遍历的节点是空的，就直接返回。
if (root==null)返回；单层循环逻辑
前序遍历是从中间到左的顺序，所以单层递归的逻辑是先取中间节点的值。代码如下：
result . add(root . val)；preorder(root.left，result)；preorder(root.right，result)；//前序遍历递归LC144 _二叉树的前序遍历类解法{public list integer前序遍历(treenode root){ list integer result=new ArrayList integer()；前序(根，结果)；返回结果；} public void preorder(TreeNode root，list integer result){ if(root==null){ return；} result . add(root . val)；//先保存中间节点preorder(root.left，result)；//处理左节点preorder(root.right，result)；//处理右节点} }//二叉树的中序遍历LC94 _中序遍历类解{公共列表整数按序遍历(treenode root){ list integer RES=new ArrayList()；inorder(root，RES)；返回res} void inorder(TreeNode root，list integer list){ if(root==null){ return；} inorder(root.left，list)；//先处理左侧节点list . add(root . val)；//中间保存当前节点inorder(root.right，list)；//先处理右节点} }//后序遍历LC145 _二叉树的后序遍历类解法{public list integer后序遍历(treenode root){ list integer RES=new ArrayList()；后序(根，RES)；返回res} void postorder(TreeNode root，list integer list){ if(root==null){ return；} postorder(root.left，list)；//先处理左边节点postorder(root.right，list)；//重新处理右节点list . add(root . val)；//保存最后一个}}
目录
//前序遍历class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack(); if (root == null) return res; stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val); if (node.right != null) { //先将右孩子入栈，因为它在最后 stack.push(node.right); } if (node.left != null) { //左孩子入栈再出栈 stack.push(node.left); } } return res; }}//中序遍历class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack(); TreeNode cur = root; while (cur != null !stack.isEmpty()) { //如果可以，一直往左下探 if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); //弹出来的肯定是叶子节点或中间节点 res.add(cur.val); //将这个节点加入list cur = cur.right; //查看当前节点是否有右节点，如果右，肯定是中间节点，如果没有，就是叶子节点，继续弹出就可以 } } return res; }}//后序遍历//再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.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; }}
3.二叉树的统一迭代法
//前序遍历class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> st = new Stack<>(); if (root != null) st.push(root); while (!st.empty()) { TreeNode node = st.peek(); if (node != null) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈） if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈） st.push(node); // 添加中节点 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。 } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st.peek(); // 重新取出栈中元素 st.pop(); result.add(node.val); // 加入到结果集 } } return result; }}//中序遍历class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> st = new Stack<>(); if (root != null) st.push(root); while (!st.empty()) { TreeNode node = st.peek(); if (node != null) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈） st.push(node); // 添加中节点 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。 if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈） } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st.peek(); // 重新取出栈中元素 st.pop(); result.add(node.val); // 加入到结果集 } } return result; }}//后序遍历class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); Stack<TreeNode> st = new Stack<>(); if (root != null) st.push(root); while (!st.empty()) { TreeNode node = st.peek(); if (node != null) { st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中 st.push(node); // 添加中节点 st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。 if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈） if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈） } else { // 只有遇到空节点的时候，才将下一个节点放进结果集 st.pop(); // 将空节点弹出 node = st.peek(); // 重新取出栈中元素 st.pop(); result.add(node.val); // 加入到结果集 } } return result; }}到此这篇关于Java开发深入分析讲解二叉树的递归和非递归遍历方法的文章就介绍到这了,更多相关Java二叉树的递归内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。