二叉树的三种遍历(递归,迭代)

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

  • 简易记法:将一个节点分为三个边,分别用不同颜色如图表示,从根节点进入从左边开始沿着边进行遍历,由下图可知,路过的红色部分依次为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; 
        }
}

上一篇:快速排序(java实现)


下一篇:PAT查找题---1028 人口普查 (20分)