树

BFS

199. 二叉树的右视图

Difficulty: 中等

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

 	public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {
                    list.add(node.val);
                }
            }
        }
        return list;
    }

剑指Offer-32.从上到下打印二叉树一

Difficulty: 中等

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回：

[3,9,20,15,7]

提示：

节点总数 <= 1000

解法同199. 二叉树的右视图，最基础的BFS。

102. 二叉树的层序遍历

相同题：剑指 Offer 32 - II. 从上到下打印二叉树 II

Difficulty: 中等

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

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

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解法同199. 二叉树的右视图，最基础的BFS。

103. 二叉树的锯齿形层序遍历

相同题：剑指 Offer 32 - III. 从上到下打印二叉树 III

Difficulty: 中等

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

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

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

解法同199. 二叉树的右视图，单数行add(val)，偶数行add(0, val)。

树的递归

104. 二叉树的最大深度

Difficulty: 简单

与剑指 Offer 55 - I. 二叉树的深度相同。

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

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

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

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

返回它的最大深度 3 。

思路：直接DFS递归即可。选左右大的，往上反映。

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

111. 二叉树的最小深度

Difficulty: 简单

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在[0, 10⁵]内
-1000 <= Node.val <= 1000

思路：用标准的BFS，或者用DFS都可以。BFS太简单就不写了，DFS递归如下：

public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    //左子树的最小深度
    int left = minDepth(root.left);
    //右子树的最小深度
    int right = minDepth(root.right);
    //如果left和right都为0，我们返回1即可，
    //如果left和right只有一个为0，说明他只有一个子结点，我们只需要返回它另一个子节点的最小深度+1即可。
    //如果left和right都不为0，说明他有两个子节点，我们只需要返回最小深度的+1即可。
    return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}

226. 翻转二叉树

相同题：剑指 Offer 27. 二叉树的镜像

Difficulty: 简单

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell的原问题启发的：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

思路：每个子树都需要交换左右->子问题--用递归。类似于交换a，b两个变量，用一个tmp暂存先被换的那边。

    //1. 前序——先换当前左右，再把子树的交换任务给递归
	public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);    
        invertTree(root.right);    
        return root;
    }
	
	//2. 后序——先把子树交换好，再换当前节点的左右。
	public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        invertTree(root.left);    
        invertTree(root.right);    
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }

	//3. 进阶玩法，直接换。其实遍历顺序还是方法2.
	public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }

	//4.也可以用BFS，一层一层去换左右，这里就不写了。

112. 路径总和

Difficulty: 简单

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

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

思路：非常基础的递归。对于子树，寻找是否有pathSum = target - root.val

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

129. 求根节点到叶节点数字之和

-Difficulty: 中等

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

思路：递归，维护一个全局变量，加起来所有值即可。

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if(root == null){
            return 0;
        }
        dfs(root, 0);
        return sum;
    }
    public void dfs(TreeNode root, int val){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            sum = sum + root.val + val * 10;
        }
        val = val * 10 + root.val;
        dfs(root.left, val);
        dfs(root.right, val);
    }
}

实际上，不需要成员变量：前序遍历，把上面的值传下去，再返回来路径和。

 	public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }

    public int helper(TreeNode root, int i) {
        if (root == null) {
            return 0;
        }
        int sum = i * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return helper(root.left, sum) + helper(root.right, sum);
    }

剑指 Offer 26. 树的子结构

Difficulty: 中等

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

3 / \ 4 5 / \ 1 2
给定的树 B：

4 / 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

**思路：双重递归。**若树B是树A的子结构，则子结构的根节点可能为树A的任意一个节点。因此，对于A的任意一个节点，都需要判断是不是从这个开始的子树包含B。

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null ){
            return false;
        }
        return aContainB(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean aContainB(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }else if(A == null){
            return false;
        }
        return A.val == B.val && aContainB(A.left, B.left) && aContainB(A.right, B.right);
    }

543. 二叉树的直径

Difficulty: 简单

考察要点：使用全局变量

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

方法1：不使用全局变量。最大直径 = Math(包括root的最大直径，左子树的最大直径，右子树的最大直径)。

每个子树都要重复计算depth，时间复杂度O(NlogN)

	public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int diaContainRoot = depth(root.left) + depth(root.right);
        int diaOfLeftSubTree = diameterOfBinaryTree(root.left);
        int diaOfRightSubTree = diameterOfBinaryTree(root.right);
        return Math.max(diaContainRoot, Math.max(diaOfLeftSubTree, diaOfRightSubTree));
    }

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

方法2：使用全局变量。递归的返回值是子树的最大深度，左右子树的最大深度+1与max去对比。

	int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;
    }

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

拓展：全局变量方法的原理与更多应用在这道题中，全局变量计算的是路径的最大值（max）。计算 max 的方式不是一次性求出来的，而是在二叉树遍历的过程中，每出现一个值，就把这个值和全局变量比较计算，算一个最大值。最终全局变量能得到全局的最大值。

实际上这利用了 max 的性质，max 是一种在线算法。简单来说，在线算法就是在计算的时候，所有的输入数据以“流”的形式一个个进来，算法每次只处理一条数据，不需要保存全部的数据。

除了 max 之外，sum、all 也都属于在线算法（all 指的是 x1 && x2 && ... && xn 这样的计算）。可以举几个其他的二叉树题目例子：

二叉树的坡度：563. Binary Tree Tilt（sum）

101. 对称二叉树

相同题：剑指 Offer 28. 对称的二叉树

Difficulty: 简单 543. 二叉树的直径能做出来，这道题就应该能做出来。

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

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

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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

方法1：递归。从root的左右子树开分，左对右，右对左。

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

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

方法2：迭代

	public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }

114. 二叉树展开为链表

Difficulty: 中等

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

**进阶：**你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

思路1：递归。 递归的特点：不用想函数的内部细节是如何处理的，我们只看其函数作用，输入与返回值。首先将根节点的左子树变成链表。其次将根节点的右子树变成链表。最后将变成链表的右子树放在变成链表的左子树的最右边。

思路2：迭代。O(１)解法。要把左边的节点放到右边，右边的节点该放在哪里呢？放在左边节点的最右侧的节点的右边，放好以后，继续往下即可。

    //思路1：递归
	public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        //将根节点的左子树变成链表
        flatten(root.left);
        //将根节点的右子树变成链表
        flatten(root.right);
        TreeNode temp = root.right;
        //把树的右边换成左边的链表
        root.right = root.left;
        //记得要将左边置空
        root.left = null;
        //找到树的最右边的节点
        while(root.right != null) {
            root = root.right;
        }
        //把右边的链表接到刚才树的最右边的节点
        root.right = temp;
    }

	//思路2: 迭代
	 public void flatten(TreeNode root) {
        while (root != null) { 
            //左子树为 null，直接考虑下一个节点
            if (root.left == null) {
                root = root.right;
            } else {
                // 找左子树最右边的节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                } 
                //将原来的右子树接到左子树的最右边节点
                pre.right = root.right;
                // 将左子树插入到右子树的地方
                root.right = root.left;
                root.left = null;
                // 考虑下一个节点
                root = root.right;
            }
        }
    }

297. 二叉树的序列化与反序列化

Difficulty: 困难

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

树中结点数在范围 [0, 10<sup>4</sup>] 内
-1000 <= Node.val <= 1000

思路：递归先序遍历获取序列化，再先序遍历反序列化。

也可以使用BFS，都不难，把null也算进去，逗号分隔，split一下就可以了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.substring(0, sb.length()-1);
    }
    private void dfs(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append("null,");
            return;
        } 
        sb.append(String.valueOf(root.val)).append(",");
        dfs(root.left, sb);
        dfs(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");
        Queue<String> queue = new LinkedList<>();
        for(String s : strs){
            queue.add(s);
        }
        return deserialize(queue);
    }
    private TreeNode deserialize(Queue<String> queue){
        if(queue.size() == 0) {
            return null;
        }
        String str = queue.poll();
        if(str.equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(str));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

树的前中后序遍历

94. 二叉树的中序遍历

Difficulty: 中等

给定一个二叉树的根节点 root ，返回它的中序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

**思路：**递归的本质就是Stack，因此可以把递归方法转换成迭代方法。

//1. 递归方法
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    inorderTraversal(root, list);
    return list;
}
private void inorderTraversal(TreeNode root, List<Integer> list){
    if(root == null){
        return;
    }
    inorderTraversal(root.left, list);
    list.add(root.val);
    inorderTraversal(root.right, list);
}

//2. 迭代方法  递归就是Stack
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {   //递归没有结束
        if (root != null) {   //相当于if(root==null) return;
            stack.push(root);  //相当于dfs(root.left); root在栈底，left更先pop出
            root = root.left;
        } else {
            root = stack.pop();   //到达最左边，开始出栈，进行处理
            list.add(root.val);   //中序
            root = root.right;  //根root处理完之后，处理root.right，相当于dfs(root.right); 
        }
    }
    return list;
}

//也可以把循环里的if换成while
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        list.add(curr.val);
        curr = curr.right;
    }
    return list;
}

比较有意思的方法：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/

144. 二叉树的前序遍历

Difficulty: 中等

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

**思路：**和中序遍历思路一样，用Stack代替递归，中序和前序的递归区别只是添加到list的顺序，用Stack也是一样。

	//1. 递归方法
	public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        inorderTraversal(root, list);
        return list;
    }
	private void inorderTraversal(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        inorderTraversal(root.left, list);
        inorderTraversal(root.right, list);
    }

	//2. 迭代方法  递归就是Stack
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {   //递归没有结束
            if (root != null) {   //相当于if(root==null) return;
                list.add(root.val);   //先序
                stack.push(root);  //相当于dfs(root.left); root在栈底，left更先pop出
                root = root.left;
            } else {
                root = stack.pop();   //到达最左边，开始出栈，进行处理
                root = root.right;  //根root处理完之后，处理root.right，相当于dfs(root.right); 
            }
        }
        return list;
    }

145. 二叉树的后序遍历

Difficulty: 中等

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

**思路：**很多人写的用到前序遍历，把左右反过来，然后reverse list，这实际上并不是后续遍历，如果需要后序做一些操作的时候是错的，只是结果对了。

正确的做法：思考与上面两道题的区别，Stack当中的根节点在它的右子树遍历结束之后才可以被删除，因此在转向右子树的时候，只能用peek()，不能用pop()。从右子树回来的时候才能pop()。

那么怎样判断是否从右子树回来的呢？如果当前节点的右节点和前一个节点相同，那就表明当前是从右节点回来的。 只需要维护一个prev节点，指向遍历的前一个节点。

 	public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode prev = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode temp = stack.peek();
                //如果当前节点的右节点和前一个节点相同，那就表明当前是从右节点回来的
                if (temp.right != null && temp.right != prev) {
                    curr = temp.right;
                } else {  //已经遍历过左右了
                    list.add(temp.val);
                    prev = temp;
                    stack.pop();
                }
            }
        }
        return list;
    }

230. 二叉搜索树中第K小的元素

Difficulty: 中等

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

**思路：中序遍历就是从小到大的顺序。可以使用DFS，也可以用94. 二叉树的中序遍历**的Stack方法。

class Solution {
    int num = 0;
    int res;

    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root, k);
        return res;
    }

    private void inorderTraversal(TreeNode node, int k) {
        if (node == null || num > k) {
            return;
        }
        inorderTraversal(node.left, k);
        num++;
        if (num == k) {
            res = node.val;
            return;
        }
        inorderTraversal(node.right, k);
    }
}

105. 从前序与中序遍历序列构造二叉树

相同题：剑指 Offer 07. 重建二叉树

Difficulty: 中等

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

**思路1：**一般做法

以preorder起点为根节点，用根节点在inorder位置确定左右子树分界，递归传入左右子树的preorder数组和inorder数组，构造左右子树。不需要copy新的数组，只需要传入新的左右边界下标。

inorder数组左右边界很简单，preorder数组左右边界计算--利用数组大小相等。

**思路2：**熟悉树遍历的本质：只需要维护一个全局变量的指针，先序+1，即可保持先序的根节点。

//1. 思路1
class Solution {
    private Map<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        map = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preLen - 1, 0, inLen - 1);
    }


    private TreeNode buildTree(int[] preorder, int pl, int pr, int il, int ir) {
        if (pl > pr || il > ir) {
            return null;
        }
        // 先序遍历的起点元素很重要
        int pivot = preorder[pl];
        TreeNode root = new TreeNode(pivot);
        int pivotIndex = map.get(pivot);
        root.left = buildTree(preorder, pl + 1, pivotIndex - il + pl,
                              il, pivotIndex - 1);
        root.right = buildTree(preorder, pivotIndex - il + pl + 1, pr,
                               pivotIndex + 1, ir);
        return root;
    }
}

//2. 思路2 更简单
class Solution {
    int idx;
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTree(preorder,0,preorder.length-1);
    }
    private TreeNode buildTree(int[] preorder, int left, int right){
        if(left>right) return null;
        TreeNode root = new TreeNode(preorder[idx]);
        int pivot = map.get(preorder[idx]);  //在left之前，就是先序遍历 先序+1
        idx++;
        root.left=buildTree(preorder,left,pivot-1);
        root.right=buildTree(preorder,pivot+1,right);
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树

Difficulty: 中等

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

与105. 从前序与中序遍历序列构造二叉树基本一样，后序从右往左，作用和先序数组一样。

	//1. 一般做法：
	public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inLen = inorder.length;
        int postLen = postorder.length;
        Map<Integer, Integer> InorderMap = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            InorderMap.put(inorder[i], i);
        }
        return buildTree(postorder, InorderMap, 0, postLen - 1, 0, inLen - 1);
    }

    private TreeNode buildTree(int[] postorder, Map<Integer, Integer> InorderMap, int postLeft, int postRight, int inLeft, int inRight) {
        if (postLeft > postRight || inLeft > inRight) {
            return null;
        }
        int pivot = postorder[postRight];
        TreeNode root = new TreeNode(pivot);
        int pivotIndex = InorderMap.get(pivot);
        root.left = buildTree(postorder, InorderMap, postLeft, pivotIndex - 1 - inLeft + postLeft,
                inLeft, pivotIndex - 1);
        root.right = buildTree(postorder, InorderMap, postRight + pivotIndex - inRight, postRight - 1,
                pivotIndex + 1, inRight);
        return root;
    }


	//2. 全局变量指针
	class Solution {
        int idx;
        Map<Integer, Integer> map;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            map = new HashMap<>();
            for(int i=0;i<inorder.length;i++){
                map.put(inorder[i],i);
            }
            idx = postorder.length-1;
            return buildTree(postorder,0,postorder.length-1);
        }
        private TreeNode buildTree(int[] postorder, int left, int right){
            if(left>right) return null;
            TreeNode root = new TreeNode(postorder[idx]);
            int pivot = map.get(postorder[idx]);
            idx--;
            root.right=buildTree(postorder,pivot+1,right);
            root.left=buildTree(postorder,left,pivot-1);
            return root;
        }
    }

889. 根据前序和后序遍历构造二叉树

Difficulty: 中等

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

思路：前序+后序遍历没办法唯一确定二叉树，中左右和左右中，左右连在一起，无法判断节点属于左子树还是右子树。因为只需要返回一种答案，可以按序遍历pre数组，当前根节点是idx，idx+1是左子树，post数组对应位置左边都当作左子树，右边都当作右子树。

	public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int preLen = pre.length;
        int postLen = post.length;
        Map<Integer, Integer> postMap = new HashMap<>();
        for (int i = 0; i < postLen; i++) {
            postMap.put(post[i], i);
        }
        return buildTree(pre, postMap, 0, preLen - 1, 0, postLen - 1);
    }

    private TreeNode buildTree(int[] pre, Map<Integer, Integer> postMap, int preLeft, int preRight, int postLeft, int postRight) {
        if (postLeft > postRight || preLeft > preRight) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preLeft]);
        if (preLeft + 1 <= preRight) {  //不能超过右边界
            int pivot = pre[preLeft + 1];
            int pivotIndex = postMap.get(pivot);
            root.left = buildTree(pre, postMap, preLeft + 1, pivotIndex - postLeft + preLeft + 1, postLeft, pivotIndex);
            root.right = buildTree(pre, postMap, preRight + pivotIndex + 2 - postRight, preRight, pivotIndex + 1, postRight - 1);
        }
        return root;
    }

后续遍历的应用

110. 平衡二叉树

相同题：剑指 Offer 55 - II. 平衡二叉树

Difficulty: 简单

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树_每个节点 _的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10⁴ <= Node.val <= 10⁴

**思路：自底向上，后续遍历，复杂度为O(N)。**如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        if (left == -1) {
            return -1;
        }
        int right = dfs(root.right);
        if (right == -1) {
            return -1;
        }
        if (left - right > 1 || right - left > 1) {
            return -1;
        }
        return 1 + Math.max(left, right);
    }

如果不用自底向上，而自顶向下，类似剑指 Offer 26. 树的子结构，每一个节点都要从上到下重新计算一边高度。平均时间复杂度O(NlogN)，最坏，链式结构O(N²)。

	public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

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

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

Difficulty: 中等

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 10⁵] 内。
-10⁹ <= Node.val <= 10⁹
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路：需要自下而上的返回结果，因此用后序遍历。

如果左右子树查到节点都不为空，则表明p和q分别在左右子树中，因此，当前节点即为最近公共祖先。
如果左右子树其中一个不为空，公共祖先一定不在空的那一边，只需要返回非空节点。

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);
    //都不等于null，说明左右各一个。
    if (left != null && right != null) {
        return root;
    }
    //一个等于null，说明一边没找到，在另一边
    return left == null ? right : left;
}

比较粗暴的方法，更容易理解：用了后续遍历，返回数量，为2时说明找到了。

class Solution {
    TreeNode ancestor;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ancestor = root;
        postOrder(root, p, q);
        return ancestor;
    }

    private int postOrder(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return 0;
        }
        int left = postOrder(root.left, p, q);
        int right = postOrder(root.right, p, q);
        if(left == 2 || right == 2){
            return 2;
        }else{
            int ret = left + right + ((root.val == p.val || root.val == q.val) ? 1 : 0);
            if(ret == 2){
                ancestor = root;
            }
            return ret;
        }
    }
}

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

Difficulty: 简单

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：可以用236. 二叉树的最近公共祖先的方法，更好的是利用二叉搜索树的性质。

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

124. 二叉树中的最大路径和

Difficulty: 困难

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 10<sup>4</sup>]
-1000 <= Node.val <= 1000

**思路：**需要将子树路径的结果汇总到上面，用后续遍历。递归返回当前子树能向父节点提供的最大路径和（最小是0，可以选择不用）——单链路贡献度，用于上一层的计算。在每一层都用以当前节点为最高处的最大路径和去更新maxPathSum，最终全局变量maxPathSum即为所求。

这道题思路和687. 最长同值路径完全一样。

class Solution {
    int sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return sum;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
		//每次都尝试更新
        sum = Math.max(sum, left + right + root.val);
        //选择大的一边区返回
        int ret = root.val + Math.max(left, right);
        //贡献度最少是0，可以选择不要这一边的
        return Math.max(ret, 0);
    }
}

687. 最长同值路径

Difficulty: 中等

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

输出:

示例 2:

输入:

输出:

注意: 给定的二叉树不超过10000个结点。树的高度不超过1000。

思路：和124. 二叉树中的最大路径和一样，树的递归。递归结果是单链路的最长同路径贡献度。

    class Solution {
        int longestUnivaluePath = 0;

        public int longestUnivaluePath(TreeNode root) {
            dfs(root);
            return longestUnivaluePath;
        }

        int dfs(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int left = dfs(root.left);
            int right = dfs(root.right);

            left = (root.left != null && root.left.val == root.val) ? left + 1 : 0;
            right = (root.right != null && root.right.val == root.val) ? right + 1 : 0;

            longestUnivaluePath = Math.max(longestUnivaluePath, left + right);
            return Math.max(left, right);   //只能选左右中最长的一条路，继续往上推，提供单链路的最长同路径
        }
    }

树的回溯

257. 二叉树的所有路径

Difficulty: 简单

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路1：根左右，先序遍历沿路添加即可。

思路2：其实这是一道典型的回溯法的题

    //1. 先序遍历
	public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        dfs(root, list, new StringBuilder());
        return list;
    }

    private void dfs(TreeNode root, List<String> list, StringBuilder path) {
        if (root == null) {
            return;
        }
        path.append(root.val);
        if (root.left == null && root.right == null) {
            list.add(path.toString());
        }
        dfs(root.left, list, new StringBuilder(path).append("->"));
        dfs(root.right, list, new StringBuilder(path).append("->"));
    }


	//2. 回溯法 共用一个StringBuilder，每层递归之后，在返回上一层之前，删除这一层添加的
	public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        backtrack(root, list, new StringBuilder());
        return list;
    }

    private void backtrack(TreeNode root, List<String> list, StringBuilder sb) {
        if (root == null) {
            return;
        }
        int preLength = sb.length();
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            list.add(sb.toString());
        } else {
            sb.append("->");
            backtrack(root.left, list, sb);
            backtrack(root.right, list, sb);
        }
        sb.setLength(preLength); //回溯 删掉这一层加的
    }

113. 路径总和(二)

Difficulty: 中等

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

思路：与257. 二叉树的所有路径相同，回溯法。

 	public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> lists=new ArrayList<>();
        dfs(root,sum, lists, new ArrayList<Integer>());
        return lists;
    }
     private void dfs(TreeNode root, int sum, List<List<Integer>> res, ArrayList<Integer> tmp) {
        if (root == null) return;
        tmp.add(root.val);
        if (root.left == null && root.right == null && sum - root.val == 0) res.add(new ArrayList<>(tmp));
        dfs(root.left, sum - root.val, res, tmp);
        dfs(root.right, sum - root.val, res, tmp);
        tmp.remove(tmp.size() - 1);
    }

437. 路径总和(三)

⚡Difficulty: 中等

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

思路一：双递归 O(N^2)

思路二：回溯用一个list保持到当前的所有可能的路径和。 平均情况下树的深度为logN，平均时间复杂度为O(NlogN)，最差情况O(N^2)

思路三：回溯+hashmap O(N) 比较难想到。key为从root到当前的路径和，value为这种路径和的个数。以当前节点结束的路径和=root到当前路径和的个数 - root到沿路结点的路径和等于target的个数。

    //方法一：双递归 给每一个结点做DFS O(N^2)
    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;
    }

    //方法二：list回溯
    class Solution {
        int cnt = 0;

        public int pathSum(TreeNode root, int sum) {
            if (root == null) {
                return cnt;
            }
            ArrayList<Integer> list = new ArrayList<>();
            // if(root!=null) list.add(root.val);
            backtrack(list, root, sum);
            return cnt;
        }

        private void backtrack(ArrayList<Integer> list, TreeNode root, int sum) {
            if (root == null) {
                return;
            }
            for (int i = 0; i < list.size(); i++) {
                list.set(i, list.get(i) + root.val);
                if (list.get(i) == sum) {
                    cnt++;
                }
            }
            list.add(root.val);
            if (root.val == sum) {
                cnt++;
            }
            backtrack(list, root.left, sum);
            backtrack(list, root.right, sum);
            //为了不影响其他路径 回溯 删除当前节点的，并把list中每个值都减回去。
            list.remove(list.size() - 1);
            for (int i = 0; i < list.size(); i++) {
                list.set(i, list.get(i) - root.val);
            }
        }
    }


    //方法三：HashMap回溯
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> preSum = new HashMap();
        preSum.put(0, 1);
        return helper(root, 0, sum, preSum);
    }

    public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
        if (root == null) {
            return 0;
        }

        currSum += root.val;
        int res = preSum.getOrDefault(currSum - target, 0);
        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

        res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
        //为了不影响其他路径，回溯
        preSum.put(currSum, preSum.get(currSum) - 1);
        return res;
    }

二叉搜索树

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

Difficulty: 简单

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：对比236. 二叉树的最近公共祖先，考虑二叉搜索树的性质。

如果root比p和q都大，最近公共祖先只可能在root的左子树。
如果root比p和q都小，最近公共祖先只可能在root的右子树。
如果介于两者之间，说明p和q一个在root的左边，一个在root的右边，最近公共祖先就是root。

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

98. 验证二叉搜索树

Difficulty: 中等

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

**思路1：递归。**根据搜索二叉树的性质，左节点都比根节点小，右节点都比根节点大，对于其中任意一个节点，在从根节点往这个节点走的过程中，这个节点的值的上界max和下界min逐渐接近。例如从node1往右走一步，下界增大成node1.val，从node2往左走一步，上界减小到node2.val，只需要检验是不是每个节点都满足在min和max之间即可。

思路2：中序遍历。搜索二叉树的中序遍历是从小到大的顺序，只需要检查是否是从小到大即可。可以用递归中序遍历，也可以用Stack迭代：94. 二叉树的中序遍历。

特殊情况：起始的边界怎么办？可以用包装类型判断是否为null，也可以用long。

	//1.递归。这里用包装类型判断是否为null来处理初始情况。
	public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    public boolean isValidBST(TreeNode root, Integer max, Integer min) {
        if (root == null) {
            return true;
        }
        if (min != null && root.val <= min) {
            return false;
        }
        if (max != null && root.val >= max) {
            return false;
        }
        return isValidBST(root.left, root.val, min)
                && isValidBST(root.right, max, root.val);
    }

	//2. 中序遍历。这里用long来处理初始情况。
	class Solution {
        long pre = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (!isValidBST(root.left)) {
                return false;
            }
            //中序
            if (root.val <= pre) {
                return false;
            }
            pre = root.val;
            return isValidBST(root.right);
        }
    }

进阶todo-剑指Offer33. 二叉搜索树的后序遍历序列

Difficulty: 中等

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

动态规划

96. 不同的二叉搜索树

Difficulty: 中等

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

**思路：**这种1到n个的题目，往往有子问题的规律，要用动态规划来做。这篇题解的画图很清晰：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h/

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= i - 1; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        
        return dp[n];
    }

Files

树.md

Latest commit

History

树.md

File metadata and controls

树

目录

BFS

树的递归

树的前中后序遍历

后序遍历的应用

树的回溯

二叉搜索树

树的动态规划

BFS

树的递归

树的前中后序遍历

后续遍历的应用

树的回溯

二叉搜索树

动态规划