前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
树的前序遍历:FBADCEGIH
中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
树的中序遍历:ABCDEFGHI
通常来说,对于二叉搜索树,我们可以通过中序遍历得到一个递增的有序序列。
后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。
树的后序遍历:ACEDBHIGF
值得注意的是,当删除树中的节点时,删除过程将按照后序遍历的顺序进行。也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。
另外,后序遍历思想在数学表达中被广泛使用。因为编写程序来解析后缀表示法更容易:
中序: 4*7-2+5
虽然使用中序遍历可以找出原始表达式, 但程序很难处理这个表达式,因为必须考虑操作符号的优先级。
后序: 4 7 2 - * 5 +
4 7 2 5
- * +
如果对这棵树进行后序遍历并使用栈来处理表达式会非常容易。每遇到一个操作符,从栈中弹出栈顶两个元素,计算并将结果返回到栈中。
层序遍历就是逐层遍历树结构。
广度优先搜索
是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。该算法从一个根节点开始,首先访问节点本身。然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推。
树中进行广度优先搜索,则访问的节点的顺序即层序遍历顺序。
树的层序遍历:FBGADICEH
递归是树的特性之一。许多树问题可以通过递归的方式来解决。
在树的问题中, 递归可以 “自顶向下” 或 “自底向上”
“自顶向下” 意味着在每个递归层级,我们将首先访问节点来计算一些值,并在递归调用函数时将这些值传递到子节点。所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。
例如, 给定一个二叉树,寻找它的最大深度:
private int answer; // don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}
根节点的深度是1
。对于每个节点,如果我们知道某节点的深度,那我们将知道它子节点的深度。因此,在调用递归函数的时候,将节点的深度传递为一个参数,那么所有的节点都知道它们自身的深度。
“自底向上”在每个递归层次上,我们首先对所有子节点递归地调用函数,然后根据返回值和根节点本身的值得到答案。这个过程可以看作是后序遍历的一种。
例如, 给定一个二叉树,寻找它的最大深度:
public int maximum_depth(TreeNode root) {
if (root == null) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);
return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}
如果我们知道一个根节点,以其左子节点为根的最大深度为l
和以其右子节点为根的最大深度为r
,也可以求得二叉树最大深度, 我们可以选择它们之间的最大值,再加上1来获得根节点所在的子树的最大深度。即 x = max(l,r)+ 1
。
这意味着对于每一个节点来说,我们都可以在解决它子节点的问题之后得到答案。
树的前序, 中序, 后序, 层序遍历是操作 N 叉树的基础, 关于树的算法题基本都是这种思想的扩展, 所以一定要熟练掌握
对于递归的两种解题思路, 如果你不确定是使用自顶向下或自底向上, 你可以先思考:
自顶向下
” 的递归来解决此问题。或者:
自底向上
” 的递归来解决此问题。