前言：一直搞不清楚自顶向下和自底向上的区别

下面从几个例子来简要分析

---

一、区分两个概念：

自顶向下：直接return 函数调用自身下一级实现，比如 return Fibonacci(n-1) + Fibonacci(n-2);
自底向上：先递归到最小单位(叶子节点)，再从最小单位往上抛结果，传递结果

---

二、具体事例分析：

/**
 * 两种遍历方向，计算最大深度
 * 自顶向下
 * 自底向上
 *
 * @Auther:sommer1111
 * @date 2020/11/10 19:05
 */
public class _11_10_Top_Down {

    //自顶向下
    private int answer;
    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);
    }

    //自底向上
    public int maximum_depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //感受一下这里是将最底层的结果往上抛
        //，因为这里的递归边界条件是叶子节点
        int left_depth = maximum_depth(root.left);
        int right_depth = maximum_depth(root.right);
        return Math.max(left_depth, right_depth) + 1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * LettCode中的题：
 * 235. 二叉搜索树的最近公共祖先
 * 236. 二叉树的最近公共祖先
 */

class Solution {

	//搜索二叉树直接可以分为比大小，定位
    //分为都在左子树、都在右子树、两边(root)
    public TreeNode lowestCommonAncestor235(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val<root.val && q.val<root.val){
        	//这里就是自顶向下
            return lowestCommonAncestor235(root.left,p,q);
        }
        if(p.val>root.val && q.val>root.val){
            return lowestCommonAncestor235(root.right,p,q);
        }
        return root;
    }


    //递归自底向上，讨论子树中是否含有某个节点
    // 如果分别在左右子树，则返回跟节点
    // 如果在同一个子树继续往下递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null ||root==p || root==q){
            return root;
        }else{
        //着也是自底向上的思想
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(left==null && right==null){
                return null;
            }

            if(left==null){
                return right;
            }

            if(right==null){
                return left;
            }

            return root;

        }
    }
}