前序、中序、后序遍历二叉树通用公式
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---
更多精彩推荐