最全的二叉树算法总结，30道题搞定大厂算法面试

朱雀 2023-09-29 18:51 113阅读 0赞

> 本文收录于 [Github·AndroidGuide][Github_AndroidGuide]

#### 文章目录 ####

*  前言
 *  二叉树的概念
 *   *  二叉树种类
     *  遍历方式
 *  递归
 *   *  1. 树的高度
     *   *  1.0 求二叉树的最大层数(最大深度)
         *  1.1 二叉树的最小深度
     *  2. 平衡树
     *   *  思路
     *  3. 两节点的最长路径
     *  4. 翻转树
     *  5. 归并两棵树
     *  6. 判断路径和是否等于一个数
     *  7. 统计路径和等于一个数的路径数量
     *  8. 子树
     *  9. 树的对称
     *  10 求二叉树的镜像
     *  11. 最小路径
 *  层次遍历
 *   *  1. 二叉树的层序遍历
     *  按之字形打印二叉树
 *  前中后序遍历
 *   *  1. 非递归实现二叉树的前序遍历
     *  2. 非递归实现二叉树的后序遍历
     *  3. 非递归实现二叉树的中序遍历
 *  BST
 *   *  1. 修剪二叉查找树
     *  2. 寻找二叉查找树的第 k 个元素
     *  3. 把二叉查找树每个节点的值都加上比它大的节点的值
     *  4. 二叉查找树的最近公共祖先
     *  5. 二叉树的最近公共祖先
     *  6. 从有序数组中构造二叉查找树
     *  7. 根据有序链表构造平衡的二叉查找树
     *  8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值
     *  9. 在二叉查找树中查找两个节点之差的最小绝对值
     *  10. 寻找二叉查找树中出现次数最多的值
 *  参考文章
 *  小结

## 前言 ##

前段时间，写了面试必备的一系列文章，反应还不错。有一些读者反馈说，能不能整理一些面试常见的算法。前段时间，我恰好总结了 LeetCode 常见的面试算法题目。

[Android 面试必备 - http 与 https 协议][Android _ - http _ https]

[Android 面试必备 - 计算机网络基本知识（TCP，UDP，Http，https）][Android _ - _TCP_UDP_Http_https]

[Android 面试必备 - 线程][Android _ -]

[Android 面试必备 - JVM 及 类加载机制][Android _ - JVM _]

[Android 面试必备 - 系统、App、Activity 启动过程][Android _ - _App_Activity]

[面试官系列- 你真的了解 http 吗][- _ http]

[面试官问， https 真的安全吗，可以抓包吗，如何防止抓包吗][https]

[java 版剑指offer算法集锦][java _offer]

[LeetCode链表知识点&题型总结][LeetCode]

**[Android\_interview github 地址][Android_interview github]**

刚开始准备刷算法题目的时候，感觉真的是好难，十道题目有九道是不会的。心中曾一万只草泥马跑过，自己怎么这么辣鸡。

![20200731145019.png][]

慢慢得，我发现算法也是一个可以通过练习慢慢成长的。

1.  首先我们要掌握基本的数据结构，数组，链表，哈希表， Set，二叉树，堆，栈等。你要知道他们有什么优缺点，适应场景是什么，时间复杂度和空间复杂度是多少。而不能知道简单的 API。
2.  接着，掌握了这些基本的数据结构之后，一些基本的算法你也要掌握以下，比如快速排序，归并排序，对排序，二分查找。这些基本的一定要掌握，面试当中经常也会问到。
3.  分类刷题，我们在力扣上面可以看到，https://leetcode-cn.com/problemset/algorithms/ ，刷题是可以按标签来的。比如链表，数组，二分查找，二叉树，动态规划等
4.  学好算法不是一日之功，需要长期的积累。建议的做法是每天做一两道题，题目不在多，贵在于理解。坚持一两个月，你会发现你的感觉逐渐好起来了

**废话不多说了，开始进入今天的正文，LeetCode链表知识点&题型总结**

## 二叉树的概念 ##

二叉树（Binary Tree）是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

一棵典型的二叉树如下图所示：

![81b2110be617eebe8abc4ac9d5e28eef.png][]

由上述的定义可以看出，二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。

### 二叉树种类 ###

**满二叉树**

对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。

**完全二叉树**

对于一棵具有n个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

**二叉排序树：**

又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

*  若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
 *  左、右子树也分别为二叉排序树；
 *  没有键值相等的节点

二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找）

**平衡二叉树**：

又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

**红黑树**：

红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

**哈夫曼树**：

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

### 遍历方式 ###

二叉树主要有四种遍历方式

*  先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
 *  中序遍历：先访问做孩子，再访问根节点和右孩子
 *  后序遍历：先访问左孩子，再访问右孩子，再访问根节点
 *  层次遍历：按照所在层数，从下往上遍历

前提：这里先给出测试中的二叉树结构，如下图所示

![13f524a1a230b34dbcd47e2f57a8ac6c.png][]

该二叉树对应的几种遍历方式的结果顺序：

*  先序遍历：10->6->4->8->14->12->16
 *  中序遍历：4->6->8->10->12->14->16
 *  后序遍历：4->8->6->12->16->14->10
 *  层次遍历：10->6->14->4->8->12->16

## 递归 ##

一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。

### 1. 树的高度 ###

#### 1.0 求二叉树的最大层数(最大深度) ####

104. Maximum Depth of Binary Tree (Easy)

[Leetcode][] / [力扣][Link 1]

这道题目的解法其实很简单

*  如果二叉树为空，二叉树的深度为0
 *  如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

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

#### 1.1 二叉树的最小深度 ####

LeetCode：Minimum Depth of Binary Tree

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

![f828a1b64775dbd528e1f9820b645363.png][]

class Solution {
        
        public int minDepth(TreeNode root) {
        
            if(root == null)
                return 0;
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
        }
    }

### 2. 平衡树 ###

110. Balanced Binary Tree (Easy)

[Leetcode][Leetcode 1] / [力扣][Link 2]

3
       / \
      9  20
        /  \
       15   7

#### 思路 ####

平衡树左右子树高度差都小于等于 1

private boolean result = true;
    
    public boolean isBalanced(TreeNode root) {
        
        maxDepth(root);
        return result;
    }
    
    public int maxDepth(TreeNode root) {
        
        if (root == null) return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        if (Math.abs(l - r) > 1) result = false;
        return 1 + Math.max(l, r);
    }

### 3. 两节点的最长路径 ###

543. Diameter of Binary Tree (Easy)

[Leetcode][Leetcode 2] / [力扣][Link 3]

Input:
    
             1
            / \
           2  3
          / \
         4   5
    
    Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

private int max = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        
        depth(root);
        return max;
    }
    
    private int depth(TreeNode root) {
        
        if (root == null) return 0;
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        max = Math.max(max, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }

### 4. 翻转树 ###

226. Invert Binary Tree (Easy)

[Leetcode][Leetcode 3] / [力扣][Link 4]

public TreeNode invertTree(TreeNode root) {
        
        if (root == null) return null;
        TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }

### 5. 归并两棵树 ###

617. Merge Two Binary Trees (Easy)

[Leetcode][Leetcode 4] / [力扣][Link 5]

Input:
           Tree 1                     Tree 2
              1                         2
             / \                       / \
            3   2                     1   3
           /                           \   \
          5                             4   7
    
    Output:
             3
            / \
           4   5
          / \   \
         5   4   7

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. 判断路径和是否等于一个数 ###

Leetcdoe : 112. Path Sum (Easy)

[Leetcode][Leetcode 5] / [力扣][Link 6]

Given the below binary tree and sum = 22,
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1
    
    return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

路径和定义为从 root 到 leaf 的所有节点的和。

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

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

437. Path Sum III (Easy)

[Leetcode][Leetcode 6] / [力扣][Link 7]

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    Return 3. The paths that sum to 8 are:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3. -3 -> 11

路径不一定以 root 开头，也不一定以 leaf 结尾，但是必须连续。

public int pathSum(TreeNode root, int sum) {
        
        if (root == null) return 0;
        int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        return ret;
    }
    
    private int pathSumStartWithRoot(TreeNode root, int sum) {
        
        if (root == null) return 0;
        int ret = 0;
        if (root.val == sum) ret++;
        ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
        return ret;
    }

### 8. 子树 ###

572. Subtree of Another Tree (Easy)

[Leetcode][Leetcode 7] / [力扣][Link 8]

Given tree s:
         3
        / \
       4   5
      / \
     1   2
    
    Given tree t:
       4
      / \
     1   2
    
    Return true, because t has the same structure and node values with a subtree of s.
    
    Given tree s:
    
         3
        / \
       4   5
      / \
     1   2
        /
       0
    
    Given tree t:
       4
      / \
     1   2
    
    Return false.

public boolean isSubtree(TreeNode s, TreeNode t) {
        
        if (s == null) return false;
        return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
        
        if (t == null && s == null) return true;
        if (t == null || s == null) return false;
        if (t.val != s.val) return false;
        return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
    }

### 9. 树的对称 ###

101. Symmetric Tree (Easy)

[Leetcode][Leetcode 8] / [力扣][Link 9]

![449606e2988ea8bcaf36665cdcb0670d.png][]

public boolean isSymmetric(TreeNode root) {
        
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode t1, TreeNode t2) {
        
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
    }

### 10 求二叉树的镜像 ###

![2ae53584ae2daa4c89bf3a34dd0ef4c9.png][]

class Solution {
        public TreeNode invertTree(TreeNode root) {
            if(root == null)
                return root;
    
            // 先保存最节点，因为 invertTree 已经变化了
            TreeNode node = root.left;
            root.left = invertTree(root.right);
            root.right = invertTree(node);
            
            return root;
        }
    }

### 11. 最小路径 ###

111. Minimum Depth of Binary Tree (Easy)

[Leetcode][Leetcode 9] / [力扣][Link 10]

树的根节点到叶子节点的最小路径长度

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

## 层次遍历 ##

使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

### 1. 二叉树的层序遍历 ###

[二叉树的层序遍历 II][II]

给定二叉树，返回其节点值的自下而上级别顺序遍历。

class Solution {
        
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
            List<List<Integer>> res = new LinkedList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if(root == null)
                return res;
            queue.add(root);
            while(!queue.isEmpty()){
        
                int count = queue.size();
                List<Integer> temp = new LinkedList<>();
                for(int i=0; i<count; i++){
        
                    TreeNode node = queue.poll();
                    temp.add(node.val);
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                // 每次都添加到第一个位置
                res.add(0, temp);
            }
            return res;
        }
    }

### 按之字形打印二叉树 ###

剑指offer：按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

*  设两个栈，s2存放奇数层，s1存放偶数层
 *  遍历s2节点的同时按照左子树、右子树的顺序加入s1，
 *  遍历s1节点的同时按照右子树、左子树的顺序加入s2

import java.util.ArrayList;
    import java.util.Stack;
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
            int flag = 1;
            if(pRoot == null)
                return res;
            s2.push(pRoot);
            ArrayList<Integer> temp = new ArrayList<Integer>();
            while(!s1.isEmpty() || !s2.isEmpty()){
                if(flag % 2 != 0){
                    while(!s2.isEmpty()){
                        TreeNode node = s2.pop();
                        temp.add(node.val);
                        if(node.left != null){
                            s1.push(node.left);
                        }
                        if(node.right != null){
                            s1.push(node.right);
                        }
                    }
                }
                if(flag % 2 == 0){
                    while(!s1.isEmpty()){
                        TreeNode node = s1.pop();
                        temp.add(node.val);
                        if(node.right != null){
                            s2.push(node.right);
                        }
                        if(node.left != null){
                            s2.push(node.left);
                        }
                    }
                }
                res.add(new ArrayList<Integer>(temp));
                temp.clear();
                flag ++;
            }
            return res;
        }
    
    }

## 前中后序遍历 ##

1
       / \
      2   3
     / \   \
    4   5   6

*  层次遍历顺序：\[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 实现。

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

① 前序

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

② 中序

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

③ 后序

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

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

144. Binary Tree Preorder Traversal (Medium)

[Leetcode][Leetcode 10] / [力扣][Link 11]

public List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
        
            TreeNode node = stack.pop();
            if (node == null) continue;
            ret.add(node.val);
            stack.push(node.right);  // 先右后左，保证左子树先遍历
            stack.push(node.left);
        }
        return ret;
    }

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

145. Binary Tree Postorder Traversal (Medium)

[Leetcode][Leetcode 11] / [力扣][Link 12]

前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

public List<Integer> postorderTraversal(TreeNode root) {
        
        List<Integer> ret = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
        
            TreeNode node = stack.pop();
            if (node == null) continue;
            ret.add(node.val);
            stack.push(node.left);
            stack.push(node.right);
        }
        Collections.reverse(ret);
        return ret;
    }

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

94. Binary Tree Inorder Traversal (Medium)

[Leetcode][Leetcode 12] / [力扣][Link 13]

public List<Integer> inorderTraversal(TreeNode root) {
        
        List<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
        
            while (cur != null) {
        
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            ret.add(node.val);
            cur = node.right;
        }
        return ret;
    }

## BST ##

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。

二叉查找树中序遍历有序。

### 1. 修剪二叉查找树 ###

669. Trim a Binary Search Tree (Easy)

[Leetcode][Leetcode 13] / [力扣][Link 14]

Input:
    
        3
       / \
      0   4
       \
        2
       /
      1
    
      L = 1
      R = 3
    
    Output:
    
          3
         /
       2
      /
     1

题目描述：只保留值在 L ~ R 之间的节点

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 (Medium)

[Leetcode][Leetcode 14] / [力扣][Link 15]

中序遍历解法：

private int cnt = 0;
    private int val;
    
    public int kthSmallest(TreeNode root, int k) {
        
        inOrder(root, k);
        return val;
    }
    
    private void inOrder(TreeNode node, int k) {
        
        if (node == null) return;
        inOrder(node.left, k);
        cnt++;
        if (cnt == k) {
        
            val = node.val;
            return;
        }
        inOrder(node.right, k);
    }

递归解法：

public int kthSmallest(TreeNode root, int k) {
        
        int leftCnt = count(root.left);
        if (leftCnt == k - 1) return root.val;
        if (leftCnt > k - 1) return kthSmallest(root.left, k);
        return kthSmallest(root.right, k - leftCnt - 1);
    }
    
    private int count(TreeNode node) {
        
        if (node == null) return 0;
        return 1 + count(node.left) + count(node.right);
    }

### 3. 把二叉查找树每个节点的值都加上比它大的节点的值 ###

Convert BST to Greater Tree (Easy)

[Leetcode][Leetcode 15] / [力扣][Link 16]

Input: The root of a Binary Search Tree like this:
    
                  5
                /   \
               2     13
    
    Output: The root of a Greater Tree like this:
    
                 18
                /   \
              20     13

先遍历右子树。

private int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        
        traver(root);
        return root;
    }
    
    private void traver(TreeNode node) {
        
        if (node == null) return;
        traver(node.right);
        sum += node.val;
        node.val = sum;
        traver(node.left);
    }

### 4. 二叉查找树的最近公共祖先 ###

235. Lowest Common Ancestor of a Binary Search Tree (Easy)

[Leetcode][Leetcode 16] / [力扣][Link 17]

_______6______
          /                \
      ___2__             ___8__
     /      \           /      \
    0        4         7        9
            /  \
           3   5
    
    For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

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 (Medium)

[Leetcode][Leetcode 17] / [力扣][Link 18]

_______3______
          /              \
      ___5__           ___1__
     /      \         /      \
    6        2       0        8
            /  \
           7    4
    
    For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

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);
        return left == null ? right : right == null ? left : root;
    }

### 6. 从有序数组中构造二叉查找树 ###

108. Convert Sorted Array to Binary Search Tree (Easy)

[Leetcode][Leetcode 18] / [力扣][Link 19]

public TreeNode sortedArrayToBST(int[] nums) {
        
        return toBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode toBST(int[] nums, int sIdx, int eIdx){
        
        if (sIdx > eIdx) return null;
        int mIdx = (sIdx + eIdx) / 2;
        TreeNode root = new TreeNode(nums[mIdx]);
        root.left =  toBST(nums, sIdx, mIdx - 1);
        root.right = toBST(nums, mIdx + 1, eIdx);
        return root;
    }

### 7. 根据有序链表构造平衡的二叉查找树 ###

109. Convert Sorted List to Binary Search Tree (Medium)

[Leetcode][Leetcode 19] / [力扣][Link 20]

Given the sorted linked list: [-10,-3,0,5,9],
    
    One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
    
          0
         / \
       -3   9
       /   /
     -10  5

public TreeNode sortedListToBST(ListNode head) {
        
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode preMid = preMid(head);
        ListNode mid = preMid.next;
        preMid.next = null;  // 断开链表
        TreeNode t = new TreeNode(mid.val);
        t.left = sortedListToBST(head);
        t.right = sortedListToBST(mid.next);
        return t;
    }
    
    private ListNode preMid(ListNode head) {
        
        ListNode slow = head, fast = head.next;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
        
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return pre;
    }

### 8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值 ###

653. Two Sum IV - Input is a BST (Easy)

[Leetcode][Leetcode 20] / [力扣][Link 21]

Input:
    
        5
       / \
      3   6
     / \   \
    2   4   7
    
    Target = 9
    
    Output: True

使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。

应该注意到，这一题不能用分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中。

public boolean findTarget(TreeNode root, int k) {
        
        List<Integer> nums = new ArrayList<>();
        inOrder(root, nums);
        int i = 0, j = nums.size() - 1;
        while (i < j) {
        
            int sum = nums.get(i) + nums.get(j);
            if (sum == k) return true;
            if (sum < k) i++;
            else j--;
        }
        return false;
    }
    
    private void inOrder(TreeNode root, List<Integer> nums) {
        
        if (root == null) return;
        inOrder(root.left, nums);
        nums.add(root.val);
        inOrder(root.right, nums);
    }

### 9. 在二叉查找树中查找两个节点之差的最小绝对值 ###

530. Minimum Absolute Difference in BST (Easy)

[Leetcode][Leetcode 21] / [力扣][Link 22]

Input:
    
       1
        \
         3
        /
       2
    
    Output:
    
    1

利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值。

private int minDiff = Integer.MAX_VALUE;
    private TreeNode preNode = null;
    
    public int getMinimumDifference(TreeNode root) {
        
        inOrder(root);
        return minDiff;
    }
    
    private void inOrder(TreeNode node) {
        
        if (node == null) return;
        inOrder(node.left);
        if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
        preNode = node;
        inOrder(node.right);
    }

### 10. 寻找二叉查找树中出现次数最多的值 ###

501. Find Mode in Binary Search Tree (Easy)

[Leetcode][Leetcode 22] / [力扣][Link 23]

1
        \
         2
        /
       2
    
    return [2].

答案可能不止一个，也就是有多个值出现的次数一样多。

private int curCnt = 1;
    private int maxCnt = 1;
    private TreeNode preNode = null;
    
    public int[] findMode(TreeNode root) {
        
        List<Integer> maxCntNums = new ArrayList<>();
        inOrder(root, maxCntNums);
        int[] ret = new int[maxCntNums.size()];
        int idx = 0;
        for (int num : maxCntNums) {
        
            ret[idx++] = num;
        }
        return ret;
    }
    
    private void inOrder(TreeNode node, List<Integer> nums) {
        
        if (node == null) return;
        inOrder(node.left, nums);
        if (preNode != null) {
        
            if (preNode.val == node.val) curCnt++;
            else curCnt = 1;
        }
        if (curCnt > maxCnt) {
        
            maxCnt = curCnt;
            nums.clear();
            nums.add(node.val);
        } else if (curCnt == maxCnt) {
        
            nums.add(node.val);
        }
        preNode = node;
        inOrder(node.right, nums);
    }

## 参考文章 ##

[Leetcode 题解 - 树][Leetcode _ -]

## 小结 ##

如果你想学好算法，建议上面二叉树的题目都刷一下。如果你只是想应付面试，主要看一下高频的面试题目即可。

*  树的递归。比如树的深度，最小深度，树的镜像。
 *  二叉树的前序遍历，中序遍历，后续遍历，记住，递归和非递归解法都要会。学会举一反三。
 *  二叉树的层序遍历，递归和非递归也都要会。
 *  常见的 BST 算法。二叉查找树的最近公共祖先（两个元素的，三个元素的，多个元素呢）。二叉树的最近公共祖先。

[点击关注我][Link 24]:[https:note.youdao.com/s/1I6][https_note.youdao.com_s_1I6]，可以获得以下**10G学习资料**和**大厂面经**

*  获取 Android 学习视频
 *  获取简历模板，教你如何优化简历，走近大厂
 *  大厂算法面试题，可以获得面试常见算法，剑指 offer 题解
 *  可以获得马士兵学习视频一份
 *  可以获得我精心整理的 Java 电子数据

[Github_AndroidGuide]: https://github.com/gdutxiaoxu/AndroidGuide
[Android _ - http _ https]: https://blog.csdn.net/gdutxiaoxu/article/details/97885526
[Android _ - _TCP_UDP_Http_https]: https://blog.csdn.net/gdutxiaoxu/article/details/97618598
[Android _ -]: https://blog.csdn.net/gdutxiaoxu/article/details/98475465
[Android _ - JVM _]: https://xujun.blog.csdn.net/article/details/98896053
[Android _ - _App_Activity]: https://xujun.blog.csdn.net/article/details/99006458
[- _ http]: https://blog.csdn.net/gdutxiaoxu/article/details/107349652
[https]: https://xujun.blog.csdn.net/article/details/107393249
[java _offer]: https://juejin.im/post/6854573217038909454
[LeetCode]: https://github.com/gdutxiaoxu/Android_interview/blob/master/leetcode/ArrayList/arraylist.md
[Android_interview github]: https://github.com/gdutxiaoxu/Android_interview
[20200731145019.png]: https://raw.githubusercontent.com/gdutxiaoxu/blog_pic/master/offer/20200731145019.png
[81b2110be617eebe8abc4ac9d5e28eef.png]: https://img-blog.csdnimg.cn/img_convert/81b2110be617eebe8abc4ac9d5e28eef.png
[13f524a1a230b34dbcd47e2f57a8ac6c.png]: https://img-blog.csdnimg.cn/img_convert/13f524a1a230b34dbcd47e2f57a8ac6c.png
[Leetcode]: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
[Link 1]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
[f828a1b64775dbd528e1f9820b645363.png]: https://img-blog.csdnimg.cn/img_convert/f828a1b64775dbd528e1f9820b645363.png
[Leetcode 1]: https://leetcode.com/problems/balanced-binary-tree/description/
[Link 2]: https://leetcode-cn.com/problems/balanced-binary-tree/description/
[Leetcode 2]: https://leetcode.com/problems/diameter-of-binary-tree/description/
[Link 3]: https://leetcode-cn.com/problems/diameter-of-binary-tree/description/
[Leetcode 3]: https://leetcode.com/problems/invert-binary-tree/description/
[Link 4]: https://leetcode-cn.com/problems/invert-binary-tree/description/
[Leetcode 4]: https://leetcode.com/problems/merge-two-binary-trees/description/
[Link 5]: https://leetcode-cn.com/problems/merge-two-binary-trees/description/
[Leetcode 5]: https://leetcode.com/problems/path-sum/description/
[Link 6]: https://leetcode-cn.com/problems/path-sum/description/
[Leetcode 6]: https://leetcode.com/problems/path-sum-iii/description/
[Link 7]: https://leetcode-cn.com/problems/path-sum-iii/description/
[Leetcode 7]: https://leetcode.com/problems/subtree-of-another-tree/description/
[Link 8]: https://leetcode-cn.com/problems/subtree-of-another-tree/description/
[Leetcode 8]: https://leetcode.com/problems/symmetric-tree/description/
[Link 9]: https://leetcode-cn.com/problems/symmetric-tree/description/
[449606e2988ea8bcaf36665cdcb0670d.png]: https://img-blog.csdnimg.cn/img_convert/449606e2988ea8bcaf36665cdcb0670d.png
[2ae53584ae2daa4c89bf3a34dd0ef4c9.png]: https://img-blog.csdnimg.cn/img_convert/2ae53584ae2daa4c89bf3a34dd0ef4c9.png
[Leetcode 9]: https://leetcode.com/problems/minimum-depth-of-binary-tree/description/
[Link 10]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
[II]: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/?spm=a2c4e.10696291.0.0.5e5719a42W3zNP
[Leetcode 10]: https://leetcode.com/problems/binary-tree-preorder-traversal/description/
[Link 11]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
[Leetcode 11]: https://leetcode.com/problems/binary-tree-postorder-traversal/description/
[Link 12]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
[Leetcode 12]: https://leetcode.com/problems/binary-tree-inorder-traversal/description/
[Link 13]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
[Leetcode 13]: https://leetcode.com/problems/trim-a-binary-search-tree/description/
[Link 14]: https://leetcode-cn.com/problems/trim-a-binary-search-tree/description/
[Leetcode 14]: https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
[Link 15]: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/description/
[Leetcode 15]: https://leetcode.com/problems/convert-bst-to-greater-tree/description/
[Link 16]: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/description/
[Leetcode 16]: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
[Link 17]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
[Leetcode 17]: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
[Link 18]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
[Leetcode 18]: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
[Link 19]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/description/
[Leetcode 19]: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
[Link 20]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/description/
[Leetcode 20]: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/
[Link 21]: https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/description/
[Leetcode 21]: https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/
[Link 22]: https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/description/
[Leetcode 22]: https://leetcode.com/problems/find-mode-in-binary-search-tree/description/
[Link 23]: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/description/
[Leetcode _ -]: https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%A0%91.md
[Link 24]: https://note.youdao.com/s/1I6XRHDF
[https_note.youdao.com_s_1I6]: https:note.youdao.com/s/1I6