Java二叉树的递归和非递归遍历方法是什么(java,开发技术)

前言

二叉树的遍历方法分为前序遍历，中序遍历，后续遍历，层序遍历。

1.递归遍历

对于递归，就不得不说递归三要素：以前序遍历为例

递归入参参数和返回值

因为要打印出前序遍历节点的数值，所以参数里需要传入List在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

publicvoidpreorder(TreeNoderoot,List<Integer>result)

确定终止条件

在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return

if(root==null)return;

单层循环逻辑

前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

result.add(root.val);preorder(root.left,result);preorder(root.right,result);

//前序遍历·递归·LC144_二叉树的前序遍历classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>result=newArrayList<Integer>();preorder(root,result);returnresult;}publicvoidpreorder(TreeNoderoot,List<Integer>result){if(root==null){return;}result.add(root.val);//先保存中间节点preorder(root.left,result);//处理左边节点preorder(root.right,result);//处理右边节点}}//中序遍历·递归·LC94_二叉树的中序遍历classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();inorder(root,res);returnres;}voidinorder(TreeNoderoot,List<Integer>list){if(root==null){return;}inorder(root.left,list);//先处理左边节点list.add(root.val);//保存中间当前的节点inorder(root.right,list);//先处理右边节点}}//后序遍历·递归·LC145_二叉树的后序遍历classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();postorder(root,res);returnres;}voidpostorder(TreeNoderoot,List<Integer>list){if(root==null){return;}postorder(root.left,list);//先处理左边节点postorder(root.right,list);//再处理右边节点list.add(root.val);//保存最后}}

2.非迭代遍历

//前序遍历classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();Stack<TreeNode>stack=newStack();if(root==null)returnres;stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();res.add(node.val);if(node.right!=null){//先将右孩子入栈，因为它在最后stack.push(node.right);}if(node.left!=null){//左孩子入栈再出栈stack.push(node.left);}}returnres;}}//中序遍历classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();if(root==null)returnres;Stack<TreeNode>stack=newStack();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){//如果可以，一直往左下探if(cur!=null){stack.push(cur);cur=cur.left;}else{cur=stack.pop();//弹出来的肯定是叶子节点或中间节点res.add(cur.val);//将这个节点加入listcur=cur.right;//查看当前节点是否有右节点，如果右，肯定是中间节点，如果没有，就是叶子节点，继续弹出就可以}}returnres;}}//后序遍历//再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<>();if(root==null)returnres;Stack<TreeNode>stack=newStack();stack.push(root);while(!stack.isEmpty()){TreeNodenode=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);//将结果反转之后就是左右中的顺序了returnres;}}

3.二叉树的统一迭代法

//前序遍历classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>result=newLinkedList<>();Stack<TreeNode>st=newStack<>();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=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);//加入到结果集}}returnresult;}}//中序遍历classSolution{publicList<Integer>inorderTraversal(TreeNoderoot){List<Integer>result=newLinkedList<>();Stack<TreeNode>st=newStack<>();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=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);//加入到结果集}}returnresult;}}//后序遍历classSolution{publicList<Integer>postorderTraversal(TreeNoderoot){List<Integer>result=newLinkedList<>();Stack<TreeNode>st=newStack<>();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=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);//加入到结果集}}returnresult;}}