递归

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

Leetcode-104. 二叉树的最大深度

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

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

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

解法：

Java

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

Leetcode-110. 平衡二叉树

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

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

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

示例 1:

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

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

解法：

Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   
    public boolean isBalanced(TreeNode root) {
   
        if (root==null) return true;
        int l = treeDepth(root.left);
        int r = treeDepth(root.right);
        return Math.abs(l-r)<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int treeDepth(TreeNode node) {
   
        if (node==null) return 0;
        return 1+Math.max(treeDepth(node.left), treeDepth(node.right));
    }
}

注意基本类型传入后是不会被改变的，

Leetcode-543. 二叉树的直径

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

示例 :

给定二叉树

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

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

解法：

Java

dfs
按照常用方法计算一个节点的深度：max(depth of node.left, depth of node.right) + 1。在计算的同时，经过这个节点的路径长度为 1 + (depth of node.left) + (depth of node.right) 。搜索每个节点并记录这些路径经过的点数最大值，期望长度是结果 - 1。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   
    public int diameterOfBinaryTree(TreeNode root) {
   
        if (root==null) return 0;
        return Math.max((getDepth(root.left)+getDepth(root.right)), 
        Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
    }
    private int getDepth(TreeNode node) {
   
        if (node==null) return 0;
        return 1+Math.max(getDepth(node.left), getDepth(node.right));
    }
}

Leetcode-226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

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

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

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

解法：

Java
为什么Max Howell做不出来。。。

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

Leetcode-617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

注意: 合并必须从两个树的根节点开始。

解法：

Java

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

Leetcode-112. 路径总和

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

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

示例:

给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解法：

Java

class Solution {
   
    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);
    }
}

Leetcode-437. 路径总和 III

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

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

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

二叉树不超过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

解法：

Java

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

Leetcode-572. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:

给定的树 s:

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

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

示例 2:

给定的树 s：

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

   4
  / \
 1   2
返回 false。

解法：

Java

class Solution {
   
    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 (s==null && t==null) return true;
        if (s==null || t==null) return false;
        if (s.val != t.val) return false;
        return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
    }
}

Leetcode-101. 对称二叉树

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

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

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

    1
   / \
  2   2
   \   \
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解法：

java

class Solution {
   
    public boolean isSymmetric(TreeNode root) {
   
        if (root==null) return true;
        return TwoSymmetricTrees(root.left, root.right);
    }
    private boolean TwoSymmetricTrees(TreeNode root1, TreeNode root2) {
   
        if (root1==null && root2==null) return true;
        if (root1==null || root2==null) return false;
        if (root1.val != root2.val) return false;
        return TwoSymmetricTrees(root1.left, root2.right) && TwoSymmetricTrees(root1.right, root2.left);
    }
}

Leetcode-111. 二叉树的最小深度

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

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

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

解法：

Java

class Solution {
   
    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;
    }
}

Leetcode-404. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

/
9 20
/
15 7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解法：

Java

class Solution {
   
    public int sumOfLeftLeaves(TreeNode root) {
   
        if (root==null) return 0;
        if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
    private boolean isLeaf(TreeNode node) {
   
        if (node == null) return false;
        return node.left==null && node.right==null;
    }
}

Leetcode-687. 最长同值路径

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

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

示例 1:

示例 2:

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

解法：

java

class Solution {
   
    private int path;
    public int longestUnivaluePath(TreeNode root) {
   
        if (root==null) return 0;
        dfs(root);
        return path;
    }
    private 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.val==root.left.val)? left+1:0;
        int rightPath = (root.right!=null && root.val==root.right.val)? right+1:0;
        path = Math.max(path, leftPath+rightPath);
        return Math.max(leftPath, rightPath);
    }
}

Leetcode-337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

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

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解法：

Java

public int rob(TreeNode root) {
   
    if (root == null) return 0;
    int val1 = root.val;
    if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
    if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
    int val2 = rob(root.left) + rob(root.right);
    return Math.max(val1, val2);
}

Leetcode-671. 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

示例 1:

输入: 
    2
   / \
  2   5
     / \
    5   7

输出: 5
说明: 最小的值是 2 ，第二小的值是 5 。

示例 2:

输入: 
    2
   / \
  2   2

输出: -1
说明: 最小的值是 2, 但是不存在第二小的值。

解法：

Java

根节点一定是最小的
如果左边值等于root值，去找左边第二小的，同理右边

class Solution {
   
    public int findSecondMinimumValue(TreeNode root) {
   
        if (root==null || (root.left==null&&root.right==null)) return -1;
        int l = root.left.val;
        int r = root.right.val;
        if (l==root.val) l = findSecondMinimumValue(root.left);
        if (r==root.val) r = findSecondMinimumValue(root.right);
        if (l==-1 && r==-1) return -1;
        if (l!=-1 && r!=-1) return Math.min(l, r);
        return l==-1? r: l;
    }
}

层次遍历

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

Leetcode-637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输入:
    3
   / \
  9  20
    /  \
   15   7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

解法：

Java
BFS

class Solution {
   
    public List<Double> averageOfLevels(TreeNode root) {
   
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
   
            int n = queue.size();
            double sum = 0;
            for (int i=0;i<n;i++) {
   
                TreeNode node = queue.remove();
                sum += node.val;
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(sum/n);
        }
        return res;
    }
}

Leetcode-513. 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

注意: 您可以假设树（即给定的根节点）不为 NULL。

解法：

Java
记录最深一层的第一个node

class Solution {
   
    public int findBottomLeftValue(TreeNode root) {
   
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode res = null;
        q.add(root);
        while(!q.isEmpty()) {
   
            int n = q.size();
            for (int i=0;i<n;i++) {
   
                TreeNode node = q.remove();
                if (i==0) res = node;
                if (node.left!=null) q.add(node.left);
                if (node.right!=null) q.add(node.right);
            }
        }
        return res.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 实现。

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

① 前序

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

Leetcode-144. 二叉树的前序遍历

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

示例:

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

输出: [1,2,3]

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

解法：

Java

递归

class Solution {
   
    public List<Integer> preorderTraversal(TreeNode root) {
   
        List<Integer> lst = new ArrayList<>();
        dfs(root, lst);
        return lst;
    }
    public void dfs(TreeNode root, List<Integer> lst) {
   
        if (root==null) return;
        lst.add(root.val);
        dfs(root.left, lst);
        dfs(root.right, lst);
    }
}

非递归
注意非递归使用的是dfs，需要用栈来存储TreeNode，与层次遍历中的queue要区分开
同时为了保持root-> left -> right的顺序，需要将right先入栈

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   
    public List<Integer> preorderTraversal(TreeNode root) {
   
        List<Integer> res = new ArrayList<>();
        if (root==null) return res;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (! stack.isEmpty()) {
   
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right!=null) stack.push(node.right);
            if (node.left!=null) stack.push(node.left);
        }
        return res;
    }
}

Leetcode-145. 二叉树的后序遍历

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

示例:

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

输出: [3,2,1]

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

解法：

Java

递归

class Solution {
   
    public List<Integer> postorderTraversal(TreeNode root) {
   
        List<Integer> lst = new ArrayList<>();
        dfs(root, lst);
        return lst;
    }
    public void dfs(TreeNode root, List<Integer> lst) {
   
        if (root==null) return;
        dfs(root.left, lst);
        dfs(root.right, lst);
        lst.add(root.val);
    }
}

Java

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

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

Leetcode-94. 二叉树的中序遍历

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

示例:

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

输出: [1,3,2]

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

解法：

Java

递归

class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
   
        List<Integer> lst = new ArrayList<>();
        this.dfs(root, lst);
        return lst;
    }
    public void dfs(TreeNode root, List<Integer> lst) {
   
        if (root==null) return ;
        dfs(root.left, lst);
        lst.add(root.val);
        dfs(root.right, lst);
    }
}

Java

非递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   
    public List<Integer> inorderTraversal(TreeNode root) {
   
        List<Integer> res = new ArrayList<>();
        if (root==null) return res;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        // stack.push(cur); 这里不要提前push进去root
        while (!stack.isEmpty() || cur!=null) {
   
            while (cur != null) {
   
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            res.add(node.val);
            cur = node.right;
        }
        return res;
    }
}

BST

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

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

Leetcode- 669. 修剪二叉搜索树

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:

示例 2:

解法：

Java

当 node.val > R，那么修剪后的二叉树必定出现在节点的左边。

类似地，当 node.val < L，那么修剪后的二叉树出现在节点的右边。

否则，我们将会修剪树的两边。

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

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

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

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

进阶：

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

解法：

Java
中序遍历得到第k小的元素

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

递归取数

class Solution {
   
    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.right, k-leftCnt-1);
        return kthSmallest(root.left, k);
    }
    private int count(TreeNode node) {
   
        if (node==null) return 0;
        return 1 + count(node.left) + count(node.right);
    }
}

Leetcode-538. 把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

解法：

Java

在递归方法中，我们维护一些递归调用过程中可以访问和修改的全局变量。首先我们判断当前访问的节点是否存在，如果存在就递归右子树，递归回来的时候更新总和和当前点的值，然后递归左子树。如果我们分别正确地递归 root.right 和 root.left ，那么我们就能正确地用大于某个节点的值去更新此节点，然后才遍历比它小的值。

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

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

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

百度百科中最近公共祖先的定义为：“对于有根树 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 为不同节点且均存在于给定的二叉搜索树中。

解法：

Java

从根节点开始遍历树
如果节点 pp 和节点 qq 都在右子树上，那么以右孩子为根节点继续 1 的操作
如果节点 pp 和节点 qq 都在左子树上，那么以左孩子为根节点继续 1 的操作
如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 pp 和节点 qq 的 LCA 了

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

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

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

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

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

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

解法：

Java

class Solution {
   
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   
        if (root==null || root==p || root==q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l!=null && r!=null) return root;
        return l==null? r: l;
    }
}

Leetcode-108. 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解法：

Java

不要再将mid元素分到left或者right中

class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
   
        return dfs(nums, 0, nums.length-1);    
    }
    private TreeNode dfs(int[] nums, int start, int end) {
   
        if (start>end) return null;
        int mid = start + (end-start)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, start, mid-1);
        root.right = dfs(nums, mid+1, end);
        return root;
    }
}

Leetcode- 109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解法：

java

关键点同样是找中间的节点

class Solution {
   
    public TreeNode sortedListToBST(ListNode head) {
   
        if (head==null) return null;
        if (head.next==null) return new TreeNode(head.val);
        ListNode preMid = getPreMid(head);
        ListNode mid = preMid.next;
        preMid.next = null;
        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    private ListNode getPreMid(ListNode head) {
   
        if (head==null) return null;
        ListNode pre = head, slow = head, fast = head;
        while (fast!=null && fast.next!=null) {
   
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return pre;
    }
}

Leetcode-653. 两数之和 IV - 输入 BST

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入:
5
/
3 6
/ \
2 4 7

Target = 9

输出: True

案例 2:

输入:
5
/
3 6
/ \
2 4 7

Target = 28

输出: False

解法：

Java

先使用中序遍历将BST顺序存储，然后用双指针进行遍历。
注意因为需要两个数相加等于k，所以l不可以等于h，指针不能够重叠

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

Leetcode-530. 二叉搜索树的最小绝对差

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

示例 :

输入:

   1
    \
     3
    /
   2

输出:
1

解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

注意: 树中至少有2个节点。

解法：

Java

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

class Solution {
   
    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);
    }
}

Leetcode-501. 二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如：

给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

解法：

Java

依然是使用中序遍历，中序遍历可以解决大部分的BST问题

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

Trie

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。

Leetcode-208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

解法：

Java

class Trie {
   
    
    class TrieNode {
   
        public char val;
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord;
        public TrieNode(char c) {
   
            val = c;
            isWord = false;
        }
    }
    
    public TrieNode root = new TrieNode(' ');
    
    public void insert(String word) {
   
        TrieNode node = root;
        for (int i=0;i<word.length();i++) {
   
            char c = word.charAt(i);
            if (node.children[c-'a']==null) node.children[c-'a'] = new TrieNode(c);
            node = node.children[c-'a'];
        }
        node.isWord = true;
    }
    
    public boolean search(String word) {
   
        TrieNode node = root;
        for (int i=0;i<word.length();i++) {
   
            char c = word.charAt(i);
            if (node.children[c-'a']==null) return false;
            node = node.children[c-'a'];
        }
        return node.isWord;
    }
    
    public boolean startsWith(String prefix) {
   
        TrieNode node = root;
        for (int i=0;i<prefix.length();i++) {
   
            char c = prefix.charAt(i);
            if (node.children[c-'a']==null) return false;
            node = node.children[c-'a'];
        }
        return true;
    }
}

另一种写法

class Trie {
   
    
    private class TrieNode {
   
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    
    private TrieNode root = new TrieNode();
    
    public Trie() {
   }
    
    public void insert(String word) {
   
        insert(word, root);
    }
    
    private void insert(String word, TrieNode node) {
   
        if (node == null) return ;
        if (word.length()==0) {
   
            node.isWord = true;
            return;
        }
        int idx = word.charAt(0)-'a';
        if (node.children[idx]==null) node.children[idx] = new TrieNode();
        insert(word.substring(1), node.children[idx]);
    }
    
    public boolean search(String word) {
   
        return search(word, root);
    }
    private boolean search(String word, TrieNode node) {
   
        if (node==null) return false;
        if (word.length()==0) return node.isWord;
        int idx = word.charAt(0)-'a';
        return search(word.substring(1), node.children[idx]);
    }
    
    public boolean startsWith(String prefix) {
   
        return startsWith(prefix, root);
    }
    private boolean startsWith(String prefix, TrieNode node) {
   
        if (node==null) return false;
        if (prefix.length()==0) return true;
        int idx = prefix.charAt(0)-'a';
        return startsWith(prefix.substring(1), node.children[idx]);
    }
}

Leetcode-677. 键值映射

实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

解法：

Java

class MapSum {
   
    
    class TrieNode {
   
        int val = 0;
        TrieNode[] children = new TrieNode[26];
    }
    
    private TrieNode root = new TrieNode();
    
    public MapSum() {
   }
    
    public void insert(String key, int val) {
   
        insert(key, val, root);
    }
    private void insert(String key, int val, TrieNode node) {
   
        if (node==null) return;
        if (key.length()==0) {
   
            node.val = val;
            return;
        }
        int idx = key.charAt(0)-'a';
        if (node.children[idx]==null) node.children[idx] = new TrieNode();
        insert(key.substring(1), val, node.children[idx]);
    }
    
    public int sum(String prefix) {
   
        return sum(prefix, root);
    }
    
    private int sum(String prefix, TrieNode node) {
   
        if (node==null) return 0;
        if (prefix.length()!=0) {
   
            int idx = prefix.charAt(0)-'a';
            return sum(prefix.substring(1), node.children[idx]);
        }
        int res = node.val;
        for (TrieNode child :node.children) {
   
            res += sum("", child);
        }
        return res;
    }
}

Leetcode 题解 - 树

递归

Leetcode-104. 二叉树的最大深度

解法：

Leetcode-110. 平衡二叉树

解法：

Leetcode-543. 二叉树的直径

解法：

Leetcode-226. 翻转二叉树

解法：

Leetcode-617. 合并二叉树

解法：

Leetcode-112. 路径总和

解法：

Leetcode-437. 路径总和 III

解法：

Leetcode-572. 另一个树的子树

解法：

Leetcode-101. 对称二叉树

解法：

Leetcode-111. 二叉树的最小深度

解法：

Leetcode-404. 左叶子之和

解法：

Leetcode-687. 最长同值路径

解法：

Leetcode-337. 打家劫舍 III

解法：

Leetcode-671. 二叉树中第二小的节点

解法：

层次遍历

Leetcode-637. 二叉树的层平均值

解法：

Leetcode-513. 找树左下角的值

解法：

前中后序遍历

Leetcode-144. 二叉树的前序遍历

解法：

Leetcode-145. 二叉树的后序遍历

解法：

Leetcode-94. 二叉树的中序遍历

解法：

BST

Leetcode- 669. 修剪二叉搜索树

解法：

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

解法：

Leetcode-538. 把二叉搜索树转换为累加树

解法：

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

解法：

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

解法：

Leetcode-108. 将有序数组转换为二叉搜索树

解法：

Leetcode- 109. 有序链表转换二叉搜索树

解法：

Leetcode-653. 两数之和 IV - 输入 BST

解法：

Leetcode-530. 二叉搜索树的最小绝对差

解法：

Leetcode-501. 二叉搜索树中的众数

解法：

Trie

Leetcode-208. 实现 Trie (前缀树)

解法：

Leetcode-677. 键值映射

解法：