递归

1、树的高度

104.maximum-depth-of-binary-tree
LeetCode

//2020.6.1
/**
*解法1：
*每个结点只访问一次
*因此时间复杂度为 O(N)
*具体思路就是深度优先遍历左边的树枝，最底层为空时的高度为0，依次+1
*/
class Solution {
    public int maxDepth(TreeNode root) {
        return getDepth(root);
    }

    public int getDepth(TreeNode root){
        if(root == null) return 0;
        int max = 0;
        max = Math.max(max,getDepth(root.left)+1);
        max = Math.max(max,getDepth(root.right)+1);
        return max;
    }
}
//简化版写法
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

2、平衡二叉树(BT)

110.balanced-binary-tree
Leetcode

算法流程：
isBalanced(root) ：判断树 root 是否平衡
特例处理：若树根节点 root 为空，则直接返回 true；
返回值：所有子树都需要满足平衡树性质，因此以下三者使用与逻辑 & 连接；
abs(self.depth(root.left) - self.depth(root.right)) <= 1 ：判断当前子树是否是平衡树；
self.isBalanced(root.left) ：先序遍历递归，判断当前子树的左子树是否是平衡树；
self.isBalanced(root.right) ：先序遍历递归，判断当前子树的右子树是否是平衡树；

depth(root) ：计算树 root 的最大高度
终止条件：当 root 为空，即越过叶子节点，则返回高度 0 ；
返回值：返回左 / 右子树的最大高度加 1 。

复杂度分析：
时间复杂度 O(NlogN)：最差情况下， isBalanced(root) 遍历树所有节点，占用 O(N)；判断每个节点的最大高度 depth(root) 需要遍历各子树的所有节点，子树的节点数的复杂度为 O(NlogN)
空间复杂度 O(N)：最差情况下（树退化为链表时)，系统递归需要使用O(N)的栈空间。

链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/balanced-binary-tree-di-gui-fang-fa-by-jin40789108/

//2020.6.2
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); 
    }

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

3、二叉树的直径

543.diameter-of-binary-tree
LeetCode

算法流程：
depth(root):返回节点的直径
终止条件：当 root 为空，即越过叶子节点，则返回深度 0 ；
返回值：返回左 / 右子树的最大高度加 1 。
max = Math.max(left+right,max) ：将每个节点的直径与最大值做比较替换

diameterOfBinaryTree(root)：返回节点的最大直径

复杂度分析：
时间复杂度：O(N),N为二叉树节点数，每个节点只访问一遍
空间复杂度：O(Height),Height为树的深度

//2020.6.3
class Solution {
    int max;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        max = Math.max(left+right,max);
        return Math.max(left,right)+1;
    }
}

4、翻转二叉树

226.invert-binary-tree
LeetCode

算法流程：
invert(TreeNode root):返回翻转过的二叉树
终止条件：当 root 为空，即越过叶子节点，则返回 null ；
返回值：已经翻转过的当前节点。
TreeNode left = root.left ：将原左儿子节点先保存起来，进入下一步翻转如不保存节点会丢失
root.left = invert(root.right) ：新的左儿子节点赋值为翻转过的原右儿子节点
root.right = invert(left) ：新的右儿子节点赋值为翻转过的原左儿子节点

复杂度分析：
时间复杂度：O(n),树中的每个节点都只被访问一次,n为树中节点个数
空间复杂度：O(n),Height为树的深度

//2020.6.3
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return invert(root);
    }
    public TreeNode invert(TreeNode root){
        if(root == null) return null;
        TreeNode left = root.left;
        root.left = invert(root.right);
        root.right = invert(left);
        return root;
    }
}

这里贴一个迭代解法。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) {
            return null;
        }
        //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //每次都从队列中拿一个节点，并交换这个节点的左右子树
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            //如果当前节点的左子树不为空，则放入队列等待后续处理
            if(tmp.left!=null) {
                queue.add(tmp.left);
            }
            //如果当前节点的右子树不为空，则放入队列等待后续处理
            if(tmp.right!=null) {
                queue.add(tmp.right);
            }

        }
        //返回处理完的根节点
        return root;
    }
}
作者：wang_ni_ma
链接：https://leetcode-cn.com/problems/invert-binary-tree/solution/dong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

两种解法的时间复杂度和空间复杂度是一样的

5、合并二叉树

617.merge-two-binary-trees
LeetCode

算法流程：
mergeTrees(TreeNode t1, TreeNode t2):返回合并过的二叉树
终止条件：
有三种情况

当 t1,t2 都为空，即两个树上都没有这个节点，那么就不用合并直接返回 null
当只有 t1 为空，就要把 t2 接到新建的树上面，返回 t2
当只有 t2 为空，就要把 t1 接到新建的树上面，返回 t1

返回值：已经合并过的二叉树。
TreeNode root = new TreeNode(t1.val + t2.val) ：当t1，t2都有值的时候，新建一个节点，值为两者之和
root.left= mergeTrees(t1.left,t2.left) ：递归处理左子树
root.right = mergeTrees(t1.right,t2.right) ：递归处理左子树

复杂度分析：
时间复杂度：O(n),n为两个树中节点少的那个个数
空间复杂度：O(n),在最坏情况下，会递归 n 层，需要 O(n) 的栈空间。

//2020.6.4
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null && t2 == null) return null;
        if(t1 == null) return t2;
        if(t2 == null) return t1;
        TreeNode root = new TreeNode(t1.val + t2.val);
        root.left= mergeTrees(t1.left,t2.left);
        root.right = mergeTrees(t1.right,t2.right);
        return root;
    }
}

6、路径总和

112.path-sum
LeetCode

算法流程：
PathSum(TreeNode root, int sum):返回是否有路径和等于sum

终止条件：

当节点为null时，直接返回false
当节点为叶子节点，且当前节点的val和sum正好相等时，返回true
两者之外的情况就继续递归

复杂度分析：
时间复杂度：O(n),n为树中节点个数
空间复杂度：O(n)

//2020.6.5
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return PathSum(root,sum);
    }

    public boolean PathSum(TreeNode root, int sum){
        if (root == null) return false;
        if (root.left == null &&root.right == null && root.val == sum) return true;
        return (PathSum(root.left,sum-root.val) || PathSum(root.right,sum-root.val));
    }
}

7、统计路径和等于一个数的路径数量

437.path-sum-iii
LeetCode

算法流程：
getSum(TreeNode root, int sum):返回除去root节点，路径和等于sum的情况之和

终止条件：

当节点为null时，直接返回0
当当前节点的val和sum正好相等时，res的值+1
两者之外的情况就继续递归其左右子树

int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
递归遍历root的左右子树，并获取当前节点的除去root节点，路径和等于sum的情况之和

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)

//2020.6.8
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
        return res;
    }

    public int getSum(TreeNode root, int sum){
        if(root == null) return 0;
        int res = 0;
        if(sum == root.val) res++;
        res += getSum(root.left,sum-root.val) + getSum(root.right,sum-root.val);
        return res;
    }
}

8、子树

572.subtree-of-another-tree
LeetCode

算法流程：
isSubtreeWithoutRoot(s,t):返回除去root节点，路径和等于sum的情况之和

终止条件：

当节点为null时，直接返回0
当当前节点的val和sum正好相等时，res的值+1
两者之外的情况就继续递归其左右子树

int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
递归遍历root的左右子树，并获取当前节点的除去root节点，路径和等于sum的情况之和

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)

//2020.6.9
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null) return false;
        return isSubtreeWithoutRoot(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t);
    }
    public boolean isSubtreeWithoutRoot(TreeNode s, TreeNode t){
        if(s == null && t == null) return true;
        if(s == null || t == null) return false;
        if(s.val != t.val) return false;
        return isSubtreeWithoutRoot(s.left,t.left) && isSubtreeWithoutRoot(s.right,t.right);
    }
}

9、树的对称

101.symmetric-tree
LeetCode

算法流程：
getSum(TreeNode root, int sum):返回除去root节点，路径和等于sum的情况之和

终止条件：

当节点为null时，直接返回0
当当前节点的val和sum正好相等时，res的值+1
两者之外的情况就继续递归其左右子树

int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
递归遍历root的左右子树，并获取当前节点的除去root节点，路径和等于sum的情况之和

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)

//2020.6.10
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return dfs(root.left,root.right);
    }

    public boolean dfs(TreeNode l,TreeNode r){
        if(l == null && r == null) return true;
        if(l == null || r == null) return false;
        if(l.val != r.val) return false;
        return dfs(l.left,r.right) && dfs(l.right,r.left);
    }
}

10.最小路径

111.minimum-depth-of-binary-tree
LeetCode

算法流程：
getSum(TreeNode root, int sum):返回除去root节点，路径和等于sum的情况之和

终止条件：

当节点为null时，直接返回0
当当前节点的val和sum正好相等时，res的值+1
两者之外的情况就继续递归其左右子树

int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
递归遍历root的左右子树，并获取当前节点的除去root节点，路径和等于sum的情况之和

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)

//2020.6.10
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        if(m1 == 0 || m2 == 0) return m1 + m2 + 1;
        return Math.min(m1,m2) + 1;
    }
}

11.左叶子之和

404.sum-of-left-leaves
LeetCode

算法流程：
getSum(TreeNode root, int sum):返回除去root节点，路径和等于sum的情况之和

终止条件：

当节点为null时，直接返回0
当当前节点的val和sum正好相等时，res的值+1
两者之外的情况就继续递归其左右子树

int res = getSum(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
递归遍历root的左右子树，并获取当前节点的除去root节点，路径和等于sum的情况之和

复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)

//2020.6.11
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if(isLeftLeave(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) +sumOfLeftLeaves(root.right);
    }

    public boolean isLeftLeave(TreeNode node){
        if(node == null) return false;
        return node.left == null && node.right == null;
    }
}

12.最长同值路径

687.longest-univalue-path
LeetCode

算法流程：
dfs(TreeNode root):返回当前节点下的最长同路径值

终止条件：

当节点为null时，直接返回0
否则继续进行深度优先遍历

int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
深度优先遍历root的左子树到叶子节点的父节点，并判断当前左叶子节点与父节点的值是否相等，相等路径值+1

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(H)

//2020.7.27
class Solution {
    private int path = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return path;
    }

    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
        int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
        path = Math.max(path,leftPath+rightPath);
        return Math.max(leftPath,rightPath);
    }
}

13.打家劫舍 III（间隔遍历）

337.house-robber-iii
LeetCode

算法流程：
看到这题我的第一想法就是，要不就是从根开始，要不就是从根的左右节点开始;从根开始的话，此时根的左右节点的值就要跳过，要去算左右节点的儿子节点，这样进行递归就可以解决了，不过递归解法很没面子啊，弟弟解法实锤了，下面贴两个其他解法，比递归提速了不止一点。
图片说明

终止条件：

当节点为null时，直接返回0
当左儿子节点不为null时，sum的值加上它的儿子节点

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(H)

这里贴一个其他解法：
https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/

//2020.7.28
class Solution {
    public int rob(TreeNode root) {
        if(root == null) return 0;
        int sum = root.val;
        if(root.left != null){
            sum+=rob(root.left.left) + rob(root.left.right);
        }
        if(root.right!=null){
            sum+=rob(root.right.left) + rob(root.right.right);
        }
        int sum2 = rob(root.left) + rob(root.right);
        return Math.max(sum,sum2);
    }
}

14.二叉树中第二小的节点

671.second-minimum-node-in-a-binary-tree
LeetCode

//2020年8月2日
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if(root == null) return -1;
        return findSMV(root,root.val);
    }
    public int findSMV(TreeNode x,int rootVal){
        if(x.val != rootVal){
            return x.val;
        }
        if(x.left ==null) return -1;
        int leftMin = findSMV(x.left,rootVal);
        int rightMin = findSMV(x.right,rootVal);
        if(leftMin == -1) return rightMin;
        if(rightMin == -1) return leftMin;
        return Math.min(leftMin,rightMin);
    }
}

层次遍历

1.二叉树的层平均值

637.average-of-levels-in-binary-tree
LeetCode
就是一个简单的层次遍历，没啥别的

//2020年8月3日
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int cnt = queue.size();
            double sum = 0;
            for (int i = 0; i < cnt; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(sum / cnt);
        }
        return ret;
    }
}

2.得到左下角的节点

513.find-bottom-left-tree-value
LeetCode

对树进行层次遍历，大概就是将节点保存在一个队列中，如果有右儿子，右儿子就先进队，因为队列是先进先出的，我们要保证最后一个是左节点。

//2020年8月4日
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> s = new LinkedList<>();
        s.add(root);
        while(!s.isEmpty()){
            root = s.poll();
            if(root.right != null) s.add(root.right);
            if(root.left != null) s.add(root.left);
        }
        return root.val;
    }
}

前中后序遍历

层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

1、层次

void bfs(TreeNode root){
        Queue<TreeNode> s = new LinkedList<>();
        s.add(root);
        while(!s.isEmpty()){
            root = s.poll();
            visit(root);
            if(root.left != null) s.add(root.left);
            if(root.right != null) s.add(root.right);
        }
}

2、前序

void dfs(TreeNode root){
    visit(root);
    dfs(root.left);
    dfs(root.right);
}

3、中序

void dfs(TreeNode root){
    dfs(root.left);
    visit(root);
    dfs(root.right);
}

4、后序

void dfs(TreeNode root){
    dfs(root.left);
    dfs(root.right);
    visit(root);
}

1.非递归实现二叉树前序遍历

二叉树的前序遍历
LeetCode

//2020年8月6日
class Solution {
    List<Integer> ret = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return ret;
        bfs(root);
        return ret;
    }

    public void bfs(TreeNode node){
        if(node == null) return;
        ret.add(node.val);
        if(node.left != null) bfs(node.left);
        if(node.right != null) bfs(node.right);
    }
}

2.非递归实现二叉树后序遍历

二叉树的后序遍历
LeetCode

//2020年8月6日
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode node = s.pop();
            if(node == null) continue;
            res.add(node.val);
            s.push(node.left);
            s.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}

上面的这个算法是有些问题在里面的，LeetCode显示这个算法在时间和空间上都不具备优势，看了一下别人的解，发现递归算法在某些情况下还是具有优势的。
图片说明
递归算法

3.非递归实现二叉树中序遍历

二叉树的中序遍历
LeetCode

这个中序遍历和前两个还不一样，大概的思路是这样的：
“中序遍历是左根右的顺序访问”，所以每访问到一个节点A，要先遍历A节点的左儿子节点，当左儿子全部出栈完毕，A再进行存值和对右儿子的遍历

//2020年8月11日
class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return ret;
        Stack<TreeNode> s = new Stack<>();
        TreeNode temp = root;
        while(!s.isEmpty() || temp != null){
            while(temp != null){
                s.push(temp);
                temp = temp.left;
            }
            TreeNode node = s.pop();
            ret.add(node.val);
            temp = node.right;
        }
        return ret;
    }
}

二叉查找树(BST)

二叉查找树的定义如下
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
（4）没有键值相等的结点。

1.修剪二叉搜索树

669.修剪二叉搜索树
LeetCode

二叉搜索树也是二叉树，是二叉树的话就可以用递归来解决问题。
先判断出口条件，当当前节点为null，那么直接返回null
剩余的就是判断当前节点的值是否超过了(L,R)这个区间
如果当前节点的val超过了R，说明当前节点的右儿子节点只会比R更大，所以直接返回当前节点的左儿子节点修剪结果

//2020年8月12日
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root == null) return null;
        if(root.val > R) return trimBST(root.left,L,R);
        if(root.val < L) return trimBST(root.right,L,R);

        root.left = trimBST(root.left,L,R);
        root.right = trimBST(root.right,L,R);
        return root;
    }
}

2.寻找二叉查找树的第 k 个元素

230.kth-smallest-element-in-a-bst
LeetCode

二叉搜索树也是二叉树，是二叉树的话就可以用递归来解决问题。
先判断出口条件，当当前节点为null，那么直接返回
关键：这是一颗二叉搜索树，二叉搜索树特性决定了它的的中序遍历就是由小到大的顺序，那么我们就可以将其中序遍历存到一个数组里，输出列表的第k-1个元素就好了

//2020年8月14日
class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return list.get(k-1);
    }

    public void inOrder(TreeNode root, int k){
        if(root == null) return ;
        if(root.left != null) inOrder(root.left,k);
        list.add(root.val);
        if(root.right != null) inOrder(root.right,k);
    }
}

图片说明
上面的方法易于理解，但是实际会多开一个空间为N的数组，占用的内存就很高，那么有没有不占用内存的方法呢？
当然有了，那就是将遍历到的节点记录下来，当num=k的时候的节点的值，就是我们所需要的值啦！

class Solution {
    int num = 0;
    int res;
    public int kthSmallest(TreeNode root, int k) {
        inOrder(root,k);
        return res;
    }
    public void inOrder(TreeNode root, int k){
        if(root == null) return ;
        if(root.left != null) inOrder(root.left,k);
        num++;
        if(num == k){res = root.val; return;}
        if(root.right != null) inOrder(root.right,k);
    }
}

图片说明

3.把二叉搜索树转换为累加树

538.convert-bst-to-greater-tree
LeetCode

二叉搜索树也是二叉树，是二叉树的话就可以用递归来解决问题。
今天不写解析了，心累了，擦

//2020年8月15日
class Solution {
    List<Integer> list = new ArrayList<>();
    public TreeNode convertBST(TreeNode root) {
        inOrder(root);
        Collections.reverse(list);
        newInOrder(root);
        return root;
    }

    public void inOrder(TreeNode root){
        if(root == null) return;
        if(root.left != null) inOrder(root.left);
        list.add(root.val);
        if(root.right != null) inOrder(root.right);
    }

    public void newInOrder(TreeNode root){
        int i = 0;
        if(root == null) return;
        if(root.left != null) newInOrder(root.left);
        int temp = root.val;
        while(temp < list.get(i)){
            root.val += list.get(i);
            i++;
        }
        if(root.right != null) newInOrder(root.right);
    }
}

4.二叉搜索树的最近公共祖先

235.lowest-common-ancestor-of-a-binary-search-tree
LeetCode

分析一下情况可以得知：
共三种情况

当p和q在当前根节点的左侧的时候(两节点的值小于root的值),向当前节点左侧深度遍历
当p和q在当前根节点的右侧的时候(两节点的值大于root的值),向当前节点右侧深度遍历
p q节点在当前节点的左右两侧的时候，直接返回当前节点

//2020年8月16日
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    return root;
    }
}

5.二叉树的最近公共祖先

236.lowest-common-ancestor-of-a-binary-tree/submissions
LeetCode

//2020年8月16日
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) return right;
        if(right == null) return left;
        return root;

    }
}

LeetCode-二叉树专题

递归

1、树的高度

2、平衡二叉树(BT)

3、二叉树的直径

4、翻转二叉树

5、合并二叉树

6、路径总和

7、统计路径和等于一个数的路径数量

8、子树

9、树的对称

10.最小路径

11.左叶子之和

12.最长同值路径

13.打家劫舍 III（间隔遍历）

14.二叉树中第二小的节点

层次遍历

1.二叉树的层平均值

2.得到左下角的节点

前中后序遍历

1.非递归实现二叉树前序遍历

2.非递归实现二叉树后序遍历

3.非递归实现二叉树中序遍历

二叉查找树(BST)

1.修剪二叉搜索树

2.寻找二叉查找树的第 k 个元素

3.把二叉搜索树转换为累加树

4.二叉搜索树的最近公共祖先

5.二叉树的最近公共祖先