二叉树的三种遍历（递归，迭代）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的三种遍历（递归，迭代），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3118字，纯文字阅读大概需要5分钟。

内容图文

• 二叉树前序遍历按照 根节点 左子树 右子树 的 顺序进行的，也就是根左右。

• 简易记法：将一个节点分为三个边，分别用不同颜色如图表示，从根节点进入从左边开始沿着边进行遍历，由下图可知，路过的红色部分依次为0，1，3，4，7，2，5，8（后面的中序遍历与后续遍历同理！）

• lc递归版本代码：

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
           List<Integer> ans = new ArrayList<>();
           return preorder_Traversal(root,ans); 
    }
     List<Integer> preorder_Traversal(TreeNode root,List<Integer> ans){
            if(root==null)
            {
                return ans ;
            }
            ans.add(root.val);//根节点
            preorder_Traversal(root.left,ans);//左子树
            preorder_Traversal(root.right,ans);//右子树
            return ans;
      }
}

• lc迭代版本：

		class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<>();// 用一个栈来维护前序顺序
            List<Integer> list = new ArrayList<>();//存放最终答案
            while(!stack.isEmpty()||root!=null) 
            {
                    while(root!=null)
                    {
                        stack.push(root); //用栈维护前序顺序，也就是可以退到最终节点的父节点。
                        list.add(root.val);
                        root = root.left;//访问过根节点之后访问左子树
                    }
                    root = stack.pop().right;//此时此节点已经是叶子节点，左为空，然后让root指向不为空之后的节点的右子树。
            }
            return list;
    }
}

二叉树中序遍历

• 二叉树前序遍历按照 左子树 根节点 右子树 的 顺序进行的，也就是 左 根 右。

• lc递归版本代码：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
           return inorder_Traversal(root,ans); 
    }
     List<Integer> inorder_Traversal(TreeNode root,List<Integer> ans){
            if(root==null)
            {
                return ans ;
            }
            inorder_Traversal(root.left,ans);//左子树
            ans.add(root.val);//根节点
            inorder_Traversal(root.right,ans);//右子树
            return ans;
      }
}

• lc迭代版本：

	class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();//存放最终答案
            Deque<TreeNode> stack = new LinkedList<>();// 用一个栈来维护前序顺序
            while(!stack.isEmpty()||root!=null)
            {
                while(root!=null)
                {
                    stack.push(root); //用栈维护中序遍历顺序，也就是可以退到最终节点的父节点。
                    root = root.left;
                }
                root = stack.pop();
                list.add(root.val); //保存根节点
                root = root.right;//此时让节点指向右子树。
            }
            return list;

    }
}

二叉树后序遍历

• 二叉树后序遍历按照 左子树 右子树 根节点 的 顺序进行的，也就是 左 右 根。（图中绿色）

• lc递归版本代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
              List<Integer> ans = new ArrayList<>();
           return postorder_Traversal(root,ans); 
    }
     List<Integer> postorder_Traversal(TreeNode root,List<Integer> ans){
            if(root==null)
            {
                return ans ;
            }
            postorder_Traversal(root.left,ans);//左子树
            postorder_Traversal(root.right,ans);//右子树
            ans.add(root.val);//根节点
            return ans;
      }
}

• lc迭代版本：

	class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<>();
            List<Integer> list = new ArrayList<>();
            TreeNode pre  = null ; 
            while(!stack.isEmpty()||root!=null)
            {
                while(root!=null)
                {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if(root.right==null||pre==root.right)//当前叶子节点没有右节点，那么就把他存入 或者 root的右节点和上一次pre相等时（最右端的情况）
                {
                        list.add(root.val);
                        pre = root;//记录状态
                        root=null; //防止root等于pre
                }
                else 
                {
                        stack.push(root);
                        root = root.right;
                }
            }
            return list; 
        }
}

内容总结

以上是互联网集市为您收集整理的二叉树的三种遍历（递归，迭代）全部内容，希望文章能够帮你解决二叉树的三种遍历（递归，迭代）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---