作者：whisper

链接：http://proprogrammar.com:443/article/617

声明：请尊重原作者的劳动，如需转载请注明出处

    在之前的章节中，我们已经介绍了如何解决树的遍历问题。我们也已经尝试过使用递归解决树的为前序遍历、中序遍历和后序遍历问题。

    事实上，递归是解决树相关问题的最有效和最常用的方法之一。本节中，我们将会介绍两种典型的递归方法。完成本章节后，你将能够运用基础的递归方法，自主解决二叉树相关问题。

运用递归解决树的问题

• “自顶向下” 的解决方案
• “自底向上” 的解决方案
• 总结

    在前面的章节中，我们已经介绍了如何利用递归求解树的遍历。 递归是解决树的相关问题最有效和最常用的方法之一。

    我们知道，树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表。 递归是树的特性之一。 因此，许多树问题可以通过递归的方式来解决。 对于每个递归层级，我们只能关注单个节点内的问题，并通过递归调用函数来解决其子节点问题。

    通常，我们可以通过 “自顶向下” 或 “自底向上” 的递归来解决树问题。

“自顶向下” 的解决方案

    “自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。 具体来说，递归函数 top_down(root, params) 的原理是这样的：

1. return specific value for null node
2. update the answer if needed                      // anwer <-- params
3. left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params
5. return the answer if needed                      // answer <-- left_ans, right_ans

    例如，思考这样一个问题：给定一个二叉树，请寻找它的最大深度。

    我们知道根节点的深度是1。 对于每个节点，如果我们知道某节点的深度，那我们将知道它子节点的深度。 因此，在调用递归函数的时候，将节点的深度传递为一个参数，那么所有的节点都知道它们自身的深度。 而对于叶节点，我们可以通过更新深度从而获取最终答案。 这里是递归函数 maximum_depth(root, depth) 的伪代码：

1. return if root is null
2. if root is a leaf node:
3.      answer = max(answer, depth)         // update the answer if needed
4. maximum_depth(root.left, depth + 1)      // call the function recursively for left child
5. maximum_depth(root.right, depth + 1)     // call the function recursively for right child

    以下的例子可以帮助你理解它是如何工作的：

    我们也提供了C ++和java代码以供参考。

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);
}

    “自底向上” 的解决方案

    “自底向上” 是另一种递归方法。 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。 通常， “自底向上” 的递归函数 bottom_up(root) 为如下所示：

1. return specific value for null node
2. left_ans = bottom_up(root.left)          // call function recursively for left child
3. right_ans = bottom_up(root.right)        // call function recursively for right child
4. return answers                           // answer <-- left_ans, right_ans, root.val

    让我们继续讨论前面关于树的最大深度的问题，但是使用不同的思维方式：对于树的单个节点，以节点自身为根的子树的最大深度x是多少？

    如果我们知道一个根节点，以其左子节点为根的最大深度为l和以其右子节点为根的最大深度为r，我们是否可以回答前面的问题？ 当然可以，我们可以选择它们之间的最大值，再加上1来获得根节点所在的子树的最大深度。 那就是 x = max（l，r）+ 1。

    这意味着对于每一个节点来说，我们都可以在解决它子节点的问题之后得到答案。 因此，我们可以使用“自底向上“的方法。下面是递归函数 maximum_depth(root) 的伪代码：

1. return 0 if root is null                 // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1  // return depth of the subtree rooted at root

    以下的例子可以帮助你理解它是如何工作的：

    我们也提供了C ++和java代码以供参考。

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
}

    总结

    了解递归并利用递归解决问题并不容易。

    当遇到树问题时，请先思考一下两个问题：

1. 你能确定一些参数，从该节点自身解决出发寻找答案吗？
2. 你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？

    如果答案都是肯定的，那么请尝试使用 “自顶向下” 的递归来解决此问题。

    或者你可以这样思考：对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 如果答案是肯定的，那么 “自底向上” 的递归可能是一个不错的解决方法。

    在接下来的章节中，我们将提供几个经典例题，以帮助你更好地理解树的结构和递归。

     算法-二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    // 自底向上
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }    
    
    // 自顶向下
    public int maxDepth2(TreeNode root) {
        res = 0;
        maxDepth(root, 0);
        return res;
    }
    
    public void maxDepth(TreeNode node, int depth) {
        if(node == null){
            res = Math.max(depth, res);
        }else{
            maxDepth(node.left, depth + 1);
            maxDepth(node.right, depth + 1);
        }
    }
}

    给出了自顶向下和自底向上两种解法

     算法-对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法：想到了中序遍历，得到左右子树结果后比较,两者结果相反
    public boolean isSymmetric(TreeNode root) {
        if(null == root){
            return true;
        }
        
        if(root.left == null && root.right == null){
            return true;
        }else if(root.left != null && root.right != null){
            if(root.left.val != root.right.val){
                return false;
            }
            
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            midOrder(root.left, left);
            midOrder(root.right, right);
            
            if(left.size() != right.size()){
                return false;
            }else{
                for(int i = 0; i < left.size(); i++){
                    // Integer比较不能用==，要用equals
                    if(!left.get(i).equals(right.get(left.size() - i - 1))){
                        return false;
                    }
                }
                
                return true;
            }
        }
        
        return false;
    }
    
    private void midOrder(TreeNode node, List<Integer> vals){
        if(node.left != null && node.right != null){
            midOrder(node.left, vals);
            vals.add(node.val);
            midOrder(node.right, vals);
        }else if(node.left != null){
            midOrder(node.left, vals);
            vals.add(node.val);
            vals.add(Integer.MAX_VALUE);
        }else if(node.right != null){
            vals.add(Integer.MAX_VALUE);
            vals.add(node.val);
            midOrder(node.right, vals);
        }else{
            vals.add(node.val);
        }
    }
}

    利用中序遍历，两者中序结果相反，代码写不得好，还可以优化，下面看另一种较快的解法

    而且这种解法是有问题的，因为中序遍历并不能确定一棵二叉树，但在leetcode上提交可以通过

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return solution(root,root);
    }

    public static boolean solution(TreeNode a,TreeNode b){
        if(a==null&&b==null)return true;
        if(b == null  || a==null )
        return false;
        if(a.val != b.val)return false;
        else
        return solution(a.right,b.left) && solution(a.left,b.right);
    }
}

    这种解法比较右子树与左子树（或者左子树与右子树），很简洁

    再说一件事，就是对于这种if...else if....else判断的情况，如果其中的语句是比较简单的返回，可以用嵌套的?:来进行判断从而一行代码完成，如上面可以写成

return a == null && b == null ? true : (b== null || a == null || a.val != b.val ? false : (solution(a.right,b.left) && solution(a.left,b.right)));

    leetcode中的不少题可以利用?:改成一行代码

     算法-路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法：更新sum，自顶向下，一行代码
    public boolean hasPathSum(TreeNode root, int sum) {
        return null == root ? false : (root.left == null && root.right == null ? root.val == sum : (hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)));
    }
}

     再次使用?:一行代码完成，自顶向下，更新sum

亲爱的读者：有时间可以点赞评论一下