Java基础算法每日5道详解(4)

淡淡的烟草味﹌ 2023-09-23 18:33 93阅读 0赞

# 101. Symmetric Tree #

**对称树**

Given the `root` of a binary tree, *check whether it is a mirror of itself* (i.e., symmetric around its center).

**Example 1:**

![https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg][https_assets.leetcode.com_uploads_2021_02_19_symtree1.jpg]

Input: root = [1,2,2,3,4,4,3]
    Output: true

**Example 2:**

![https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg][https_assets.leetcode.com_uploads_2021_02_19_symtree2.jpg]

Input: root = [1,2,2,null,3,null,3]
    Output: false

## leetcode代码 ##

# 104. Maximum Depth of Binary Tree #

**二叉树的最大深度**

Given the `root` of a binary tree, return *its maximum depth*.

A binary tree’s **maximum depth** is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Example 1:**

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ptCPzawy-1670866158609)(https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg)\]

Input: root = [3,9,20,null,null,15,7]
    Output: 3

**Example 2:**

Input: root = [1,null,2]
    Output: 2

## leetcode代码 ##

# 108. Convert Sorted Array to Binary Search Tree #

将排序数组转换为二叉搜索树

Given an integer array `nums` where the elements are sorted in **ascending order**, convert *it to a **height-balanced** binary search tree*.

A **height-balanced** binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

**Example 1:**

![https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg][https_assets.leetcode.com_uploads_2021_02_18_btree1.jpg]

Input: nums = [-10,-3,0,5,9]
    Output: [0,-3,9,-10,null,5]
    Explanation: [0,-10,5,null,-3,null,9] is also accepted:

![https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg][https_assets.leetcode.com_uploads_2021_02_18_btree2.jpg]

**Example 2:**

![https://assets.leetcode.com/uploads/2021/02/18/btree.jpg][https_assets.leetcode.com_uploads_2021_02_18_btree.jpg]

Input: nums = [1,3]
    Output: [3,1]
    Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

## leetcode代码 ##

# 110. Balanced Binary Tree #

平衡二叉树

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

> a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

**Example 1:**

![https://assets.leetcode.com/uploads/2020/10/06/balance\_1.jpg][https_assets.leetcode.com_uploads_2020_10_06_balance_1.jpg]

Input: root = [3,9,20,null,null,15,7]
    Output: true

**Example 2:**

![https://assets.leetcode.com/uploads/2020/10/06/balance\_2.jpg][https_assets.leetcode.com_uploads_2020_10_06_balance_2.jpg]

Input: root = [1,2,2,3,3,null,null,4,4]
    Output: false

**Example 3:**

Input: root = []
    Output: true

## leetcode代码 ##

/**
     * 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 {
        
        public boolean isBalanced(TreeNode root) {
        
            if(root==null) return true;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
            stack.push(root);
            while(!stack.isEmpty()){
        
                TreeNode node = stack.pop();
                if((node.left==null || node.left!=null && map.containsKey(node.left)) &&(node.right==null || node.right!=null && map.containsKey(node.right))){
        
                    int left = node.left==null?0:map.get(node.left);
                    int right = node.right==null?0:map.get(node.right);
                    if(Math.abs(left-right) > 1) return false;
                    map.put(node, Math.max(left, right)+1);
                }else{
        
                    if(node.left!=null && !map.containsKey(node.left)){
        
                        stack.push(node);
                        stack.push(node.left);
                    }else{
        
                        stack.push(node);
                        stack.push(node.right);
                    }
                }
            }
            return true;
        }
    
    }

# 111. Minimum Depth of Binary Tree #

二叉树的最小深度

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

**Note:** A leaf is a node with no children.

**Example 1:**

![https://assets.leetcode.com/uploads/2020/10/12/ex\_depth.jpg][https_assets.leetcode.com_uploads_2020_10_12_ex_depth.jpg]

Input: root = [3,9,20,null,null,15,7]
    Output: 2

**Example 2:**

Input: root = [2,null,3,null,4,null,5,null,6]
    Output: 5

## leetcode代码 ##

[https_assets.leetcode.com_uploads_2021_02_19_symtree1.jpg]: https://img-blog.csdnimg.cn/img_convert/d5eb10f2d571026846f6d1878b316ee5.jpeg
[https_assets.leetcode.com_uploads_2021_02_19_symtree2.jpg]: https://img-blog.csdnimg.cn/img_convert/cf13bc78ab16e051bdbe57e47abedf5e.jpeg
[https_assets.leetcode.com_uploads_2021_02_18_btree1.jpg]: https://img-blog.csdnimg.cn/img_convert/9c0c89f044410350a6c2a3e28cd67c47.jpeg
[https_assets.leetcode.com_uploads_2021_02_18_btree2.jpg]: https://img-blog.csdnimg.cn/img_convert/1c0f349cd1ad7000808d586e1dfa8422.jpeg
[https_assets.leetcode.com_uploads_2021_02_18_btree.jpg]: https://img-blog.csdnimg.cn/img_convert/51e56525aa39f9b7c43601456be81f26.jpeg
[https_assets.leetcode.com_uploads_2020_10_06_balance_1.jpg]: https://img-blog.csdnimg.cn/img_convert/d33ab5fddc01eb282b1cb8d061cf0e0b.jpeg
[https_assets.leetcode.com_uploads_2020_10_06_balance_2.jpg]: https://img-blog.csdnimg.cn/img_convert/ec1d6eb073302a9e5e0919dd9b1b7c3d.jpeg
[https_assets.leetcode.com_uploads_2020_10_12_ex_depth.jpg]: https://img-blog.csdnimg.cn/img_convert/4a8d793f59e244dd706f0198dd3952ff.jpeg