【LeetCode】二叉树问题：典型操作

太过爱你忘了你带给我的痛 2022-10-29 09:12 111阅读 0赞

### 基操 ###

#### [剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.] ####

难度简单86收藏分享切换为英文接收动态反馈

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

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

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

**题解**

*  非递归用广搜

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

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

难度简单445收藏分享切换为英文接收动态反馈

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

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]

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

**示例 2：**

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

**题解**

非递归：广搜

class Solution { 
        public int minDepth(TreeNode root) { 
            LinkedList<TreeNode> queue = new LinkedList<>();
            if(root == null){ 
                return 0;
            }
            queue.addLast(root);
    
            int level = 1;
            while(queue.size() != 0){ 
                int size = queue.size();
                for(int i = 0 ; i < size ; i ++){ 
                    TreeNode now = queue.pop();
                    if(now.right == null && now.left == null){ 
                        return level;
                    }
                    if(now.right != null){ 
                        queue.addLast(now.right);
                    }
                    if(now.left != null){ 
                        queue.addLast(now.left);
                    }
                }
                level ++;
            }
    
            throw new RuntimeException();
        }
    }

递归

class Solution {
        public int minDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            if(root.left == null && root.right == null){
                return 1;
            }
    
            int res = Integer.MAX_VALUE;
            if(root.left != null){
                res = Math.min(res , minDepth(root.left));
            }
            if(root.right != null){
                res = Math.min(res , minDepth(root.right));
            }
    
            return res + 1;
        }
    }

#### [226. 翻转二叉树][226.] ####

难度简单750收藏分享切换为英文接收动态反馈

翻转一棵二叉树。

**示例：**

输入：

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

输出：

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

**题解**

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

#### [100. 相同的树][100.] ####

难度简单560收藏分享切换为英文接收动态反馈

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

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

**示例 1：**

![在这里插入图片描述][20210210230019519.png]

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

**题解**

class Solution { 
        public boolean isSameTree(TreeNode p, TreeNode q) { 
            if(p == null && q == null){ 
                return true;
            }
            if(p == null || q == null){ 
                return false;
            }
            if(p.val != q.val){ 
                return false;
            }
            return isSameTree(p.left , q.left) && isSameTree(p.right , q.right);
        }
    }

#### [101. 对称二叉树][101.] ####

难度简单1231收藏分享切换为英文接收动态反馈

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

例如，二叉树 `[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

**题解**

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if(root == null){ 
                return true;
            }
            return isSame(root , root);
        }
    
        boolean isSame(TreeNode r1 , TreeNode r2){ 
            if(r1 == null && r2 == null){ 
                return true;
            }
    
            if(r1 == null || r2 == null){ 
                return false;
            }
    
            if(r1.val != r2.val){ 
                return false;
            }
    
            return isSame(r1.left , r2.right) && isSame(r1.right , r2.left);
        }
    }

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

难度中等432收藏分享切换为英文接收动态反馈

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]

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

**示例 2：**

输入：root = []
    输出：0

**示例 3：**

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

**题解**

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

#### [110. 平衡二叉树][110.] ####

难度简单585收藏分享切换为英文接收动态反馈

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

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]

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

**示例 2：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]

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

**示例 3：**

输入：root = []
    输出：true

**题解**

class Solution { 
        boolean res = true;
        public boolean isBalanced(TreeNode root) { 
            if(root == null){ 
                return true;
            }
    
            getHeight(root);
            return res;
        }
    
        int getHeight(TreeNode root){ 
            if(root == null){ 
                return 0;
            }
    
            int leftH = getHeight(root.left);
            int rightH = getHeight(root.right);
        
            res = res && (Math.abs(leftH - rightH) <= 1);
            return Math.max(leftH , rightH) + 1 ;
        }
    }

[Offer 55 - I.]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[111.]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221024/141f4cca77994287b199844b021d837e.png
[226.]: https://leetcode-cn.com/problems/invert-binary-tree/
[100.]: https://leetcode-cn.com/problems/same-tree/
[20210210230019519.png]: /images/20221024/1439aa26a059452d8fa4b005f888b366.png
[101.]: https://leetcode-cn.com/problems/symmetric-tree/
[222.]: https://leetcode-cn.com/problems/count-complete-tree-nodes/
[Link 1]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221024/c5205c54da8e420ea8073729079ca159.png
[110.]: https://leetcode-cn.com/problems/balanced-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: /images/20221024/71242c0042404118a157e106b9706536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: /images/20221024/fe65a9936bc24564b26774dd38212262.png