leetcode——二叉树、二叉查找树

r囧r小猫 2022-09-05 12:39 220阅读 0赞

### leetcode——二叉树、二叉查找树 ###

*   *  104. 二叉树的最大深度
     *  111. 二叉树的最小深度
     *  226. 翻转二叉树
     *  100. 相同的树
     *  222. 完全二叉树的节点个数
     *  110. 平衡二叉树
     *  112. 路径总和
     *  404. 左叶子之和
     *  257. 二叉树的所有路径
     *  113. 路径总和 II
     *  129. 求根节点到叶节点数字之和
     *  235. 二叉搜索树的最近公共祖先
     *  98. 验证二叉搜索树
     *  230. 二叉搜索树中第K小的元素
     *  236. 二叉树的最近公共祖先

## 104. 二叉树的最大深度 ##

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

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

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

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

/  
9 20  
/  
15 7

返回它的最大深度 3 。

## 111. 二叉树的最小深度 ##

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

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

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

示例 1：

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

示例 2：

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

提示：

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

思路：很容易会觉得跟上一题一样，就是递归左右子树，然后返回一个小的+1，如果该树存在左右孩子节点，那么这样确实没错。但是有反例，如下，当根节点连接的左或右子树为空时，结果为1，答案是5，就错了。补上相应的条件即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]

## 226. 翻转二叉树 ##

翻转一棵二叉树。

示例：

输入：

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

输出：

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

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

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

## 100. 相同的树 ##

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = \[1,2,3\], q = \[1,2,3\]  
输出：true

示例 2：

输入：p = \[1,2\], q = \[1,null,2\]  
输出：false

示例 3：

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

提示：

两棵树上的节点数目都在范围 [0, 100] 内
    -104 <= Node.val <= 104

## 222. 完全二叉树的节点个数 ##

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中节点的数目范围是[0, 5 * 104]
    0 <= Node.val <= 5 * 104
    题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

## 110. 平衡二叉树 ##

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

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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] 内
    -104 <= Node.val <= 104

## 112. 路径总和 ##

给你二叉树的根节点 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

## 404. 左叶子之和 ##

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

示例：

/ \\  
9 20  
/ \\  
15 7

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

## 257. 二叉树的所有路径 ##

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

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

示例:

输入:

1  
/ \\  
2 3  
\\  
5

输出: \[“1->2->5”, “1->3”\]

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

## 113. 路径总和 II ##

给你二叉树的根节点 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

/**
     * 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 {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        
            if(root == null)
                return res;
            rootPath(root, targetSum, paths);
            return res;
        }
    
        public void rootPath(TreeNode root, int targetSum, List<Integer> paths){
        
            if(root == null)
                return;
            if(root.left == null && root.right == null){
        
                if(root.val == targetSum){
        
                    paths.add(root.val);
                    res.add(new ArrayList<>(paths));
                    paths.remove(paths.size() - 1);
                    return;
                }
            }
            paths.add(root.val);
            rootPath(root.left, targetSum - root.val, paths);
            rootPath(root.right, targetSum - root.val, paths);
            paths.remove(paths.size() - 1);
        }
    }/**
     * 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 {
        
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        
            if(root == null)
                return res;
            rootPath(root, targetSum, paths);
            return res;
        }
    
        public void rootPath(TreeNode root, int targetSum, List<Integer> paths){
        
            if(root == null)
                return;
            if(root.left == null && root.right == null){
        
                if(root.val == targetSum){
        
                    paths.add(root.val);
                    res.add(new ArrayList<>(paths));
                    paths.remove(paths.size() - 1);
                    return;
                }
            }
            paths.add(root.val);
            rootPath(root.left, targetSum - root.val, paths);
            rootPath(root.right, targetSum - root.val, paths);
            paths.remove(paths.size() - 1);
        }
    }

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

给你一个二叉树的根节点 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

## 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 {
        
        TreeNode res = null;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            lca(root, p, q);
            return res;
        }
    
        public void lca(TreeNode root, TreeNode p, TreeNode q){
        
            if((root.val - p.val) * (root.val - q.val) <= 0){
        
                res = root;
            }else if(root.val < p.val && root.val < q.val){
        
                lca(root.right, p, q);
            }else{
        
                lca(root.left, p, q);
            }
        }
    }

## 98. 验证二叉搜索树 ##

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

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

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

示例 1:

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

示例 2:

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

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

给定一个二叉搜索树的根节点 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 <= 104
    0 <= Node.val <= 104

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

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

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

百度百科中最近公共祖先的定义为：“对于有根树 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, 105] 内。
    -109 <= Node.val <= 109
    所有 Node.val 互不相同 。
    p != q
    p 和 q 均存在于给定的二叉树中。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root == null || root == p || root == q){
        
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null)
                return right;
            if(right == null)
                return left;
            return root;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1MjczNg_size_16_color_FFFFFF_t_70]: /images/20220829/591545041d3c441b98a7c5b7d518820d.png