BM25. [二叉树的后序遍历]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM25. 二叉树的后序遍历

https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&sfm=github&channel=nowcoder

二叉树的遍历主要分为深度优先遍历（dfs）和广度优先遍历（bfs）。深度优先遍历就会使用栈，广度优先遍历使用队列。

「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；

「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；

「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点；

遍历代码框架如下

//前序遍历
private void preOrder(TreeNode root) {
        if (root == null)
            return;
        hanlder(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
//中序遍历
    private void inOrder(TreeNode root) {
        if (root == null)
            return;
        inOrder(root.left, list);
        hanlder(root);
        inOrder(root.right, list);

    }
//后序遍历
    private void postOrder(TreeNode root) {
        if (root == null)
            return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        hanlder(root);
    }

所以重点就来了，前中后序遍历标识的根节点输出的时时间，前序遍历就是输出根节点在遍历左右子树之前，中序遍历就是遍历完左子树然后就输出根节点然后遍历右子树，后序遍历是先遍历左子右子树再输出根节点。

存在如下二叉树图，大家试一试是否能够快速写出输出前中后序遍历。

前序遍历{12,5,18,2,9,15,19}

中序遍历{2, 5, 9, 12, 15, 18, 19}

后续遍历{2, 9, 5, 15, 19, 18, 12}

这块有两个特性大家需要注意，第一BST（搜索二叉树）的中序遍历是从小到大的，我给的例子就是一个搜索二叉树，所以中序遍历{2, 5, 9, 12, 15, 18, 19}。另外需要深刻理解一下后序遍历，因为后序遍历可以从下向上将子树的信息带上来，很多问题可以直接使用后序遍历来解决。为了让大家直观感受上个图看看

完整代码

public int[] preorderTraversal (TreeNode root) {
        List<Integer> result = new ArrayList();
        preOrder(root, result);
        return reverse(result);
    }

    //使用额外的list进行存储
    private void preOrder(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    //使用额外的list进行存储
    private void ineOrder(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        preOrder(root.left, list);
        list.add(root.val);
        preOrder(root.right, list);
    }


    //使用额外的list进行存储
    private void postOrder(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        preOrder(root.left, list);
        preOrder(root.right, list);
        list.add(root.val);
    }


    private int[] reverse(List<Integer> list){
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i]= list.get(i);
        }
        return ret;
    }