19.面试算法-树的深度优先遍(一)

1. 深入理解前中后序遍历

深度优先遍历有前中后三种情况，大部分人看过之后就能写出来，很遗憾大部分只是背下来的，稍微变换一下就废了。

我们再从二叉树的角度看递归，每次遇到递归，都按照前面说的四步来写，可以更好地写出正确的递归算法。

第一步：从小到大递推，分情况讨论

第二步：明确结束条件，初步确定入参

第三步：将等价关系变成方法调用，完成代码

第四步：从大到小画图推演

我们接下来就一步步看怎么做：

第一步：从小到大递推，分情况讨论

我们就以这个二叉树为例，这个树在很多题目都会用到：

  3
 / \
9  20
  /  \
 15   7

我们知道前中后序就是看父节点与左右孩子相比的访问顺序，前序就是中左右，中序就是左中右，后序就是左右中。我们先选一个最小的子树：

  20
  / \
15   7

假如20为head，则此时前序访问顺序应该是：

list.add(root);//20被访问
preorder(root.left);//继续访问15  
preorder(root.right); //继续访问7

验证一下，正好是20 15 7，没问题，然后再向上访问，看node(3)的情况：

list.add(root);//3被访问
preorder(root.left);//继续访问，得到9
preorder(root.right); //继续访问以node(20)为父节点的子树

此时先得到3，在得到9，之后递归preorder(root.right);的结果就是我们上一步的，合在一起就是需要的结果 3 9 20 15 7。

第二步：明确结束条件，初步确定入参

这里的递归什么时候结束呢？很明显应该是root=null的时候。一般来说链表和二叉树问题的终止条件都包含当前访问的元素为null。

那入参是什么呢？首先就是要访问的这个子树的根结点root，然后要将结果保存起来的，所以还应该有个list，每次满足要求就将结果放进来。

第三步：将等价关系变成方法调用，完成代码

到此为止，我们就能将完整代码写出来了：

public void preorder(TreeNode root, List<Integer> res) {
	if (root == null) {
		return;
	}
	res.add(root.val);
	preorder(root.left, res);
	preorder(root.right, res);
}

第四步 从大到小 画图推演

写完之后对不对呢？我们可以画个调用图看一下，因为是两个递归函数，如果比较复杂。我们可以少画几组。下图中的序号就是递归的完整过程：

从图中可以看到，当root的一个子树为null的时候还是会执行递归，进入之后发现root==null了，然后就开始返回。这里我们要特别注意res.add()的时机对不对，将其进入顺序依次写出来就是需要的结果。

这个明确之后再debug或者检查就容易很多，刚开始学习递归建议多画几次，熟悉之后就不必再画了。

另外注意一个问题，有时候题目给的方法不方便直接递归，我们需要再写一个自己的方法包一下递归过程。例如上 面前序遍历的问题，题干给的是这样的结构：

class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		preorder(root, res);
		return res;
	}
}

这个方面不方便直接递归，我们希望在每次递归过程里处理res，此时可以自己创建一个preorder()方法，这样做是完全可以的。

前序遍历写出来之后，中序和后序遍历就不难理解了，中序是左中右，后序是左右中。代码如下：

public  void preOrderRecur(TreeNode head) {
	if (head == null) {
		return;
	}
	preOrderRecur(head.left);
	System.out.print(head.val + " ");
	preOrderRecur(head.right);
}

后序：

public static void postOrderRecur(TreeNode head) {
	if (head == null) {
		return;
	}
	postOrderRecur(head.left);
	postOrderRecur(head.right);
	System.out.print(head.value + " ");
}

接下来我们就一起来分析一些经典的二叉树题目。

2. 深度和高度专题

给定二叉树 [3,9,20,null,null,15,7]，如下图

  3
 / \
9  20
   / \
  15  7

然后LeetCode给我们造了一堆的题目：

【1】 LeetCode104 二叉树的最大深度:给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点 的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。例如上面的例子返回结果为最大深度为3。

【2】 LeetCode110 判断平衡二叉树：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡 二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

【3】 LeetCode111 二叉树的最小深度：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。上面的例子返回结果为2。

这三个题看起来挺像的，我们就一起来用上面的思路来逐步分析。

2.1 最大深度问题

首先看一下104题找最大深度:给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明：叶子节点是指没有子节点的节点。例如上面的例子返回结果为最大深度为3。

我们先看一个简单情况：

  3             3           3        
 / \           /             \
9  20         9              20 

对于node(3)，最大深度自然是左右子结点+1，左右子节点有的可能为空，只要有一个，树的最大高度就是 1+1=2。

然后再增加几个结点，并增加几种情况：

  3             3           3           3
 / \           / \         / \           \
9  20         9  20       9  20          20 
  /  \          /              \        /  \ 
 15   7        15               7      15   7

很显然相对于node(20)，最大深度自然是左右子结点+1，左右子节点有的可能为空，只要有一个，树的最大高度就 是1+1=2，用代码表示就是

int depth = 1 + max(leftDepth, rightDepth);

。而对于3，则是左右子树深度最大的那个然后再+1，具体谁更大，则不必关心。所以对于node(3)的判断逻辑就是：

int leftDepth = getDepth(node.left); // 左
int rightDepth = getDepth(node.right); // 右
int depth = 1 + max(leftDepth, rightDepth); // 中

对于int leftDepth = getDepth(node.left) ，很显然这里的left是node(9)，执行一次getDepth()就返回1了。

而对于rightDepth = getDepth(node.right);这里的right是node(20)，node(20)的最大值是多少呢？显然要先计算getDepth(node(20))才知道。具体怎么算呢？交给下层来处理吧，getDepth(node(20))重新按照一样的过程来找。

通过二叉树可以非常方便的理解递归的执行过程，从这里我们可以看到，递归只处理当前这一层和下一层之间的关系，并不关心下层和下下层之间的关系。这就像老子只管养好儿子，至于孙子怎么样，那是儿子的事，你也不能瞎掺合。只要将儿子一代养好就上对得起祖宗，下对得起万代了。

然后就是什么时候结束呢，这里也比较简单，仍然是执行到root == null返回0就行了。

至于入参，自然是要处理的子树的根节点root，而返回值则是当前root所在子树的最大高度。所以合并在一起就是：

public int maxDepth(TreeNode root) {
	if (root == null) {
		return 0;
	}
	int leftHeight = maxDepth(root.left);
	int rightHeight = maxDepth(root.right);
	return Math.max(leftHeight, rightHeight) + 1;
}

这个对不对呢？可以画个图推演一下看看。

这个题我们需要先将左右子树的结果拿到之后才能计算Math.max(leftHeight, rightHeight) + 1。这是不是与后序遍历非常像呢？先解决好左右子孩子的问题再处理当前结点，这就是后序遍历的拓展问题。

有人会发现，如果通过层次遍历是不是也能解决呢？我们在层次遍历里说过，分层的时候每次都能获得一层的元素，那统计一下一共有几层自然不是问题。

2.2 平衡树问题

LeetCode110 判断平衡二叉树：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

这里的要求是二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。先补充一个问题，高度和深度怎么区分呢？

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

有点绕是吗？废话不多说，直接看图，能懂就行：

关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1，其他地方还有将其视为0的，但是毕竟刷题用LeetCode，就不管其他的了。

言归正传，我们仍然先看一个最简单的情况：

  3             3           3        
 / \           /             \
9  20         9              20 

很显然只有两层的时候一定是平衡的，为什么呢？对于node(3)，如果左右孩子只有一个，那么高度差就是1，如果左右子孩子都有或者都没有，则高度差为0。如果增加一层会怎么样呢？

  3             3           3           3
 / \           / \         / \           \
9  20         9  20       9  20          20 
  /  \          /              \        /  \ 
 15   7        15               7      15   7

对于node(3)，需要同时知道自己左右子树的最大高度差是否<2。

• 当节点root 左 / 右子树的高度差 < 2，则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1（ max(left, right) + 1 ）；
• 当节点root 左 / 右子树的高度差 ≥ 2，则返回 -1 ，代表此子树不是平衡树 。

也就是这里要完成两个工作：判断两个子树高度差与2的关系，返回最大高度或者是否为平衡树，如果是后者则直接退出就行了，如果是前者则还要返回最大高度，让上层能够继续判断。例如上面图中，node(20)是平衡的，所以返回最大高度2。然后上层node(3)发现左子树高度是0，而右子树是2，所以不平衡。所以就有：

int left = recur(root.left);
int right = recur(root.right);
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;

我们此时就写出了核心递归，然后再看终止条件。很显然，if (root == null) return 0;仍然是必要的，图中 node(9)，node(15)，node(7)的触底反弹都需要。

假如子树已经不平衡了，我们就不需要再递归了，直接返回就行，比如这个树：

               5            
              / \         
             3   4        
            / \   \    
           1   2   6    
                    \
                     7   

对于node(4)发现高度差大于1了，返回-1，之后node(5)检测到 right=-1 就不必再比较了，因为已经有子树不平衡了，直接返回-1即可。所以我们要加一下left或者right直接就返回了-1的情况，也就是：

private int recur(TreeNode root) {
	if (root == null) return 0;
	int left = recur(root.left);
	if(left == -1) return -1;
	int right = recur(root.right);
	if(right == -1) return -1;
	return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}

之后根据题目要求再套一个方法：

public boolean isBalanced(TreeNode root) {
	return recur(root) != -1;
}

这就是我们想要的结果，这种也是先获得左右子树的情况，最后处理自己，也是后序遍历的拓展。

2.3 最小深度

LeetCode111 二叉树的最小深度：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最 短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。

上面两个问题都用到了最大深度的问题，那最大深度里直接将Max改成Min行不行呢？自然是不行的，为什么呢？ 遍历顺序上依然是后序遍历(因为要比较递归返回之后的结果)，但在处理中间节点的逻辑上，最大深度很容易解， 最小深度可有一个误区。

这里的关键问题是题目中说的：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

注意是叶子节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！所以，如果我们这么判断就错了：

int leftDepth = getDepth(node.left);
int rightDepth = getDepth(node.right);
int result = 1 + min(leftDepth, rightDepth);
return result;

如果这么求的话，没有左孩子的分支会算为最短深度。 所以这里的核心问题仍然是分析终止条件：

• 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
• 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
• 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

代码整理出来就是这样：

class Solution {
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}

		if (root.left == null && root.right == null) {
			return 1;
		}

		int min_depth = Integer.MAX_VALUE;
		if (root.left != null) {
			min_depth = Math.min(minDepth(root.left), min_depth);
		}
		if (root.right != null) {
			min_depth = Math.min(minDepth(root.right), min_depth);
		}
		return min_depth + 1;
	}
}

遍历的顺序为后序(左右中)，可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

貌似这个题用层次遍历也行是吧？后面再讨论。