前序、中序、后序遍历二叉树通用公式

1. 二叉树的遍历

看这是一个二叉树，通过前序、中序和后序遍历的节点顺序如下

前序遍历：A->B->D->E->H->C->F->I->J->G

中序遍历：D->B->H->E->A->I->F->J->C->G

后序遍历：D->H->E->B->I->J->F->G->C->A

接下来我们以前序遍历为例，说明一下遍历的规则

简言之，前序遍历的规则就是：先遍历当前二叉树，再遍历左子树，最后遍历右子树

我们需要记住的一个公式就是：中左右，即先自身、再左边、后右边

注意：我这里用的概念是“树”，而不是“节点”，就是把每一个节点都当成一颗树

根据规则，先遍历当前树，当前树的根节点是A，所以首先遍历的就是A

接下来要遍历A的左子树，也就是以B为根节点的二叉树

把B作为一棵独立的树进行前序遍历

根据规则，先遍历当前树的根节点B，所以目前的遍历次序就是A->B

接下来要遍历B的左子树，也就是以D为根节点的二叉树

把D作为一棵独立的树进行前序遍历

根据规则，先遍历当前树的根节点D，所以目前的遍历次序就是A->B->D

接下来要遍历D的左子树，但是D没有左子树了

所以要再看看D的右子树，但是D也没有右子树了

所以就要往回走了，回到B

此时B当前节点和左子树都已经遍历完了，根据“中左右”的顺序，接下来要遍历E树了

把E作为一棵独立的树进行前序遍历

根据规则，先遍历当前树的根节点E，所以目前的遍历次序就是A->B->D->E

接下来要遍历E的左子树，也就是以H为根节点的二叉树

把H作为一棵独立的树进行前序遍历

根据"中左右"的顺序，先遍历当前树的根节点H，所以目前的遍历次序就是A->B->D->E->H

接下来要遍历H的左子树，但是H没有左子树，也没有右子树了

所以就要往回走，回到E，遍历E的右子树，但是E的右子树也没有了

接着回到B，最后回到A，此时A的当前节点和左子树都已经遍历完成

所以要遍历A的右子树，也就是二叉树C

把C作为一棵独立的树进行前序遍历

根据“中左右”的次序，先遍历当前树的根节点C，所以目前的遍历次序就是A->B->D->E->H->C

依次类推

接着遍历的节点就是FIJG，所以前序遍历的顺序就是：A->B->D->E->H->C->F->I->J->G

同样的中序遍历的顺序就是“左中右”、后序遍历的顺序就是“左右中”

左右的相对位置不变，前、中、后指的其实就是“中”在“左右”中的位置

2. 代码实现

还是以前序遍历为例，根据“中左右”的通用公式

采用递归的方法，一次拿到每棵树的左、中、右三个节点的内容

然后再按照中、左、右的次序加入一个列表，就能实现二叉树的前序遍历了

2.1 前序遍历

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List<Integer> left = preorderTraversal(root.left);
    List<Integer> right = preorderTraversal(root.right);

    result.add(root.val);
    result.addAll(left);
    result.addAll(right);

    return result;
}

2.2 中序遍历

中序遍历也是几乎同样的代码

只不过在加入列表的顺序改成左、中、右就可以了

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List<Integer> left = inorderTraversal(root.left);
    List<Integer> right = inorderTraversal(root.right);

    result.addAll(left);
    result.add(root.val);
    result.addAll(right);

    return result;
}

2.3 后序遍历

后续遍历的话加入列表的顺序改成左、中、右

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    List<Integer> left = postorderTraversal(root.left);
    List<Integer> right = postorderTraversal(root.right);

    result.addAll(left);
    result.addAll(right);
    result.add(root.val);

    return result;
}

行文至此，是不是发现遍历二叉树三种方法的算法实现已经完全掌握了

文/戴先生@2021年5月16日

---end---

更多精彩推荐