vlambda博客
学习文章列表

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


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---


更多精彩推荐