二叉树

递归三要素

1. 确定递归函数的参数和返回类型
2. 确定终止条件
3. 单个递归逻辑

递归函数什么时候需要返回值？

• 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
• 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先(opens new window)中介绍）
• 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

有返回值时应该仔细思考当该节点为空时，即递归到最深处应该返回什么值？假如为boolean类型的返回值一定返回true吗？不一定！！！

二叉树怎么使用回溯？

https://leetcode.cn/problems/unique-binary-search-trees-ii/

由于二叉树的每个节点都是引用，并且不好记录个数，如果还像一般情况去进行回溯根本不好解决，也不知道该在哪里回溯。所以我们换一种方式，我们在遍历一个区间时，使用列表将这个区间所有满足的二叉树记录下来，这个就保证循环过程中构造出来的二叉树不会丢失，最后循环遍历列表，以这种方式间接完成回溯。最后将这层构造的二叉树返回给上一层

class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> resList = new ArrayList<>();
        return f(1,n);
         
    }
    public List<TreeNode> f(int left,int right){
        List<TreeNode> resList = new ArrayList<>();
        if(left > right){
            resList.add(null);
            return resList;
        }
        for(int i = left;i <= right;i++){
           List<TreeNode> leftList = f(left,i - 1);
           List<TreeNode> rightList = f(i+1,right);

           for(TreeNode le : leftList){
                for(TreeNode rig : rightList){
                    TreeNode node = new TreeNode(i);
                    node.left = le;
                    node.right = rig;
                    resList.add(node);
                }
           }
           
        }
        return resList;
    }
}

最近公共祖先I

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

如果找到一个节点，则直接返回该节点不用继续向下搜索了，因为公共祖先不可能在该节点下方（感觉有点贪心的思想）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { // 递归结束条件
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}

最深叶节点的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/

方法一：想到了要可能要有两个返回值，但是一开始就被大脑否定了，因为根本就没有做过两个返回值的题目。结果真的要使用两个返回值，使用pair来作为返回值，key来返回最近父节点，value来返回自底向上的高度，当返回左右子树的高度时，谁的高度高那变相的证明它的深度大，进而根据高度找到最近父节点

class Solution {
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        Pair<TreeNode,Integer> res = dfs(root);
        return res.getKey();
    }
    public Pair<TreeNode,Integer> dfs(TreeNode node){
        if(node == null){
            return new Pair<>(null,0);
        }
        Pair<TreeNode,Integer> left = dfs(node.left);
        Pair<TreeNode,Integer> right = dfs(node.right);
        if(left.getValue() > right.getValue()){
            return new Pair<>(left.getKey(),left.getValue() + 1);
        }else if(right.getValue() > left.getValue()){
            return new Pair<>(right.getKey(),right.getValue() + 1);
        }
        return new Pair<>(node,right.getValue() + 1);
    }
}

方法二：在递归参数上维护一个深度变量，向下递归的过程中不断的让深度加1，当递归触发终止条件时，与当前最大深度对比取最大值来维护一个**全局最大深度，**然后在遍历过程中遇见左右子树高度相等时，还需要将左右子树的最大深度与全局最大深度对比，如果和全局最大深度相同，则说明该节点是当前左右子树最深叶节点的公共祖先，然后继续向上回溯去找公共祖先

class Solution {
    int maxDeepth = 0;
    TreeNode res;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        res = root;
        dfs(root,0);
        return res;
    }
    public int dfs(TreeNode node , int deepth){
        if(node == null){
            maxDeepth = Integer.max(maxDeepth,deepth);
            return deepth;
        }
        int left = dfs(node.left,deepth+1);
        int right = dfs(node.right,deepth+1);

        if(left == right && left == maxDeepth){
            res = node;
        }
        return Integer.max(left,right);
    }
}