【code基础】树的三种遍历的常规解法

树的中序遍历有三种解法，包括：

• 递归 （好理解，代码简单，但效率不高）
• 借助栈的迭代方法
• 莫里斯遍历

1.递归

     List<Integer> res = new ArrayList<>();
    //前序
    public List<Integer> preorderTraversal(TreeNode root) {
            if (root == null) return res;
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
            return res;
        }

    //中序
    public List<Integer> inorderTraversal(TreeNode root) {
            //递归的边界条件，返回res即对res不做操作
            if (root == null) return res;
            //保证如下顺序，一定是先遍历，再add
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);

            return res;
        }

    //后序
    public List<Integer> postorderTraversal(TreeNode root) {
            //递归的边界条件，返回res即对res不做操作
            if (root == null) return res;
            //保证如下顺序，一定是先遍历，再add
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            res.add(root.val);

            return res;
    }

2.借助于栈做迭代

        //前序--迭代方法-栈保存顺序
        public List<Integer> preorderTraversal2(TreeNode root) {
            if (root == null) return res;

            Stack<TreeNode> st = new Stack<>();
            st.push(root);
            while (!st.isEmpty()){
                TreeNode pop = st.pop();
                res.add(pop.val);
                //后进先出
                if (pop.right!=null) st.push(pop.right);
                if (pop.left!=null) st.push(pop.left);
            }
            return res;
        }

      // 中序--迭代方法-栈保存顺序
      public List<Integer> inorderTraversal(TreeNode root) {
            if (root == null) return res;
            Stack<TreeNode> st = new Stack<>();
            while (root!=null ||!st.isEmpty()){
                //遍历左子树
                while (root !=null){
                    st.push(root);
                    root = root.left;
                }
                //左子树遍历完了,取左子树最左下的结点，加入res
                root= st.pop();
                res.add(root.val);
                //遍历最下结点的右子树
                root = root.right;
            }
            return res;
        }

    // 后序--迭代方法-栈+被访问指针保存顺序
      public List<Integer> postorderTraversal1(TreeNode root) {
            if (root == null) return res;
            TreeNode pre = null; //已遍历过的指针
            Stack<TreeNode> st = new Stack<>();
            while (root!=null ||!st.isEmpty()){
                //遍历左子树
                while (root !=null){
                    st.push(root);
                    root = root.left;
                }
                //左子树遍历完了,取左子树最左下的结点
                root= st.pop();
                //出栈条件： 右结点为空
                if (root.right == null || root.right == pre){
                    res.add(root.val);
                    pre = root;
                    root = null;
                }
                //右子树不空的时候，根结点继续入栈，遍历右结点
                else {
                    st.push(root);
                    root = root.right;
                }
            }
            return res;
        }