4.树（四）

题目汇总：https://leetcode-cn.com/tag/tree/

230. 二叉搜索树中第K小的元素中等[✔]

235. 二叉搜索树的最近公共祖先简单[✔]

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

257. 二叉树的所有路径简单[✔]

297. 二叉树的序列化与反序列化困难（不会）

337. 打家劫舍 III中等（理解题意）

404. 左叶子之和简单[✔]

429. N叉树的层序遍历中等

437. 路径总和 III简单（不简单）

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

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:

示例 2:

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

思路一：递归+中序遍历（我的想法）

一棵二叉搜索树的中序遍历结果一定是严格递增的序列，则第 k-1 个元素就是第 k 小的元素。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了60.28%的用户
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> res = new ArrayList<>();
        if(root == null || k == 0)
            return 0;
        inorder(root, res);
        if(k >= 1 && res.size() >= k) {
            return res.get(k-1);
        }
        return 0;
        
    }

    private void inorder(TreeNode root,List<Integer> res){
        if(root != null){
            inorder(root.left, res);
            res.add(root.val);
            inorder(root.right, res);
        }   
    }
}

思路二：二分查找（评论区的想法）

查找左子树节点个数为leftN,如果K<=leftN,则所查找节点在左子树上.
若K=leftN+1,则所查找节点为根节点
若K>leftN+1,则所查找节点在右子树上,按照同样方法查找右子树第K-leftN个节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int kthSmallest(TreeNode root, int k) {
        int leftNum = findChild(root.left);
        if(k == leftNum + 1){
            return root.val;
        } 
        else if(k <= leftNum){
            return kthSmallest(root.left, k);
        }else{
            return kthSmallest(root.right, k - leftNum - 1);//这里容易弄错
        }
    }

    //查找子节点个数
    public int findChild(TreeNode root){
        if(root == null)
            return 0;
        return findChild(root.left) + findChild(root.right) + 1;
    }
}

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 为不同节点且均存在于给定的二叉搜索树中。

思路：利用二叉搜索树的特性递归（我的想法）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：6 ms, 在所有 Java 提交中击败了99.87%的用户
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;
        //如果p、q的值都小于root，说明p q 肯定在root的左子树中
        //如果p、q的值都大于root，说明p q 肯定在root的右子树中
        //如果一个在左一个在右 则说明此时的root为对应的最近公共祖先
        if(p.val < root.val && q.val <root.val){ 
            return lowestCommonAncestor(root.left, p, q);
        }else if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }else{
            return root;
        }
        
    }
}

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 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 为不同节点且均存在于给定的二叉搜索树中。

思路：递归（我可以有思路）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：7 ms, 在所有 Java 提交中击败了99.90%的用户
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)
            return null;
        if(p == root || q == root)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null)    return right;
        if(right == null)   return left;
        return root;
        
    }
}

257. 二叉树的所有路径简单

给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点

思路：DFS+递归（我的思路）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :12 ms, 在所有 Java 提交中击败了30.85%的用户
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root, "", res);
        return res;

    }
    private void dfs(TreeNode root, String cur,List<String> res){
        if(root == null)
            return;
        cur += root.val;
        if(root.left == null && root.right == null){//当前节点是叶子节点
             res.add(cur);
        }else{// 当前节点不是叶子节点
            dfs(root.left, cur + "->", res);
            dfs(root.right, cur + "->", res);
        }           
    }
}

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

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

思路：BFS（我有思路，序列化会做，反序列化不会）

代码来自评论区MeteorCh的解法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {//执行用时：26 ms, 在所有 Java 提交中击败了48.65%的用户
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder builder=new StringBuilder();
        LinkedList<TreeNode> stack=new LinkedList<>();
        stack.offer(root);
        while (!stack.isEmpty()){
            TreeNode node=stack.poll();
            if (node!=null){
                builder.append(node.val);
                stack.offer(node.left);
                stack.offer(node.right);
            }else
                builder.append("#");
            builder.append(",");
        }
        return builder.toString();
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] splits=data.split(",");
        if (splits[0].equals("#"))
            return null;
        TreeNode root=new TreeNode(Integer.parseInt(splits[0]));
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        for (int i=1;i<splits.length;++i){
            TreeNode node=queue.poll();
            if (node==null)
                continue;
            if (!splits[i].equals("#")) {
                node.left=new TreeNode(Integer.parseInt(splits[i++]));
                queue.offer(node.left);
            }else
                ++i;
            if (!splits[i].equals("#")) {
                node.right=new TreeNode(Integer.parseInt(splits[i]));
                queue.offer(node.right);
            }
        }
        return root;
        
    }
}

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

337. 打家劫舍 III中等

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

示例 2:

思路一：暴力递归（我的思路，时间效率太低）

如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。这句话是问题的关键。在评论区看到一种比喻很是恰当，根节点是爷爷，一个爷爷最多两个儿子，四个孙子。4 个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：979 ms, 在所有 Java 提交中击败了12.94%的用户
    public int rob(TreeNode root) {
        if(root == null)    return 0;
        int money = root.val;
        if(root.left != null){
            money += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money += rob(root.right.left) + rob(root.right.right);
        }
    return Math.max(money, rob(root.left) + rob(root.right));
    }
}

思路二：（效率高的）

来自https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为：
当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱。
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int rob(TreeNode root) {
        int[] result = robInternal(root);
        return Math.max(result[0], result[1]);
}

    public int[] robInternal(TreeNode root) {
        if (root == null) return new int[2];
        int[] result = new int[2];

        int[] left = robInternal(root.left);
        int[] right = robInternal(root.right);

        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = left[0] + right[0] + root.val;

        return result;

    }
}

404. 左叶子之和简单

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

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

思路：递归（我的想法）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null)
            return 0;
        int sum = 0;
        //root.left是叶子节点
        if(root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + sum;
    }
}

429. N叉树的层序遍历中等

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :

返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
说明:
树的深度不会超过 1000。
树的节点总数不会超过 5000。

思路：BFS

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了57.95%的用户
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while(len > 0){
                Node node = queue.poll();
                list.add(node.val);
                for(Node n:node.children){
                    queue.offer(n);
                }
                len--;
            }
            res.add(list);
        }
    return res;
        
    }
}

437. 路径总和 III简单

给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：

思路一：双重递归

这道题真的不能算简单吧，知道用递归做，但是写不好代码。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：29 ms, 在所有 Java 提交中击败了70.11%的用户
    int num = 0;
    //每个结点都可能成为路径中的起始结点，用来遍历树中所有结点
    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        dfs(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);
        return num;

    }
    //对于树中每个结点，以该结点为起始结点，往下找出所有和等于sum的路径
    public void dfs(TreeNode root, int sum){
        if(root == null)
            return;
        sum -= root.val;
        if(sum == 0){
            num++;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
}

思路二：DFS+回溯

代码来自评论区，还不够懂。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了99.65%的用户
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        //设置路径和符合条件即res+1的前提（0=pathSum-sum）
        map.put(0, 1);
        return helper(root, map, sum, 0);
    }
    int helper(TreeNode root, HashMap<Integer, Integer> map, int sum, int pathSum){
        int res = 0;
        if(root == null) return 0;
        //将当前所在节点的值加到走过的路径值的和中
        pathSum += root.val;
        //getOrDefault(Object key,V defaultValue)
        // 以上方法为返回指定键（Object key）所映射的值，若无则直接返回所设置的默认值（V defaultValue）
         //累加上到当前节点为止有多少条路径和符合条件（此处若是pathSum-sum==0,则返回1，在map中若存在当前pathSum-sum对应值 
        //的key则对应value的值则必不为0，为1或大于1，若无此key则返回方法默认值0）  
        res += map.getOrDefault(pathSum - sum, 0);
        //此处是计数到当前节点为止有多少条自上而下的节点路径和等于pathSum，并将其存入map
        // （亦或是更新pathSum对应的路径数，若先前有和值为pathSum的路径则取出其条数先前加上当前的一条）
        map.put(pathSum, map.getOrDefault(pathSum, 0) + 1);
        //往左子树以及右子树依次统计
        // 再加上res-->到当前节点为止可能出现的和值符合pathSum的路径数（统计范围即为头节点到当前节点）
        res = helper(root.left, map, sum, pathSum) + helper(root.right, map, sum, pathSum) + res;
        // 在返回前，将到当前节点为止的和值pathSum的条数计-1，防止影响后面其他未走完路径的统计
        //由于路径和值只能自上而下，所以在当前节点返回前（节点返回条件为下一节点为空，
        // 即为最后节点或者最后节点返回后遍历完依次往上递归返回，返回意味着pathSum到当前节点已自上而下的累加遍历完）  
        map.put(pathSum, map.get(pathSum) - 1);
        return res;
    }
}