LeetCode简单题目(二叉树相关)(#100 #101 #104 #107 #108 #110 #111 #112)-8道

梦里梦外; 2023-05-29 05:30 3阅读 0赞

> leetcode题库中共有350道简单题目。  
> 本文记录已解决的题目和代码。  
> 本文中的序号是leetcode题目中的真实序号。

### 文章目录 ###

*  100 相同的树
 *   *  描述
     *  代码
     *  更好的解法
 *  101 对称二叉树
 *   *  描述
     *  代码
     *  大神解法
     *  迭代解法
     *  简化的迭代
 *  104 二叉树的最大深度
 *   *  描述
     *  代码
     *  迭代法
 *  107 二叉树的层次遍历 II
 *   *  描述
     *  代码
     *  \# 大神代码
     *  大佬详细代码
 *  108 将有序数组转换为二叉搜索树
 *   *  描述
     *  大神代码1-递归
     *  大神代码2-递归
 *  110 平衡二叉树
 *   *  描述
     *  代码
     *  大神代码
 *  111 二叉树的最小深度
 *   *  描述
     *  代码
     *  大神解法BFS
     *  其它解法
 *  112 路径总和
 *   *  描述
     *  代码
     *  大佬迭代方法

# 100 相同的树 #

## 描述 ##

给定两个二叉树，编写一个函数来检验它们是否相同。  
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。  
示例 1:  
输入:  
1  
/ \\  
2 3  
1  
/ \\  
2 3  
\[1,2,3\], \[1,2,3\]  
输出: true  
示例 2:  
输入: 1  
/  
2  
1  
\\  
2  
\[1,2\], \[1,null,2\]  
输出: false  
示例 3:  
输入: 1  
/ \\  
2 1  
1  
/ \\  
1 2  
\[1,2,1\], \[1,1,2\]  
输出: false

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            p_list,q_list = [],[]
            self.get_list(p,p_list)
            self.get_list(q,q_list)
            return p_list == q_list
        # 递归遍历   
        def get_list(self,node,n_list):
            if not node:
                n_list.append(0)
                return None
            n_list.append(node.val)
            self.get_list(node.left,n_list)
            self.get_list(node.right,n_list)

## 更好的解法 ##

> 链接：https://leetcode-cn.com/problems/same-tree/solution/xiang-tong-de-shu-by-leetcode/

class Solution:
        def isSameTree(self, p, q):
            """
            :type p: TreeNode
            :type q: TreeNode
            :rtype: bool
            """    
            # p and q are both None
            if not p and not q:
                return True
            # one of p and q is None
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return self.isSameTree(p.right, q.right) and \
                   self.isSameTree(p.left, q.left)

# 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  
说明:  
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

## 代码 ##

class Solution:
        left_count,right_count = 0,0
        def isSymmetric(self, root: TreeNode) -> bool:
            tree_list = []
            
            if root:
                if root.left and root.right:
                    if root.left.val != root.right.val:
                        return False
            else:
                return True
            self.get_list(root,tree_list)
            len_tree_list = len(tree_list)
            for i in range(len_tree_list//2):
                if tree_list[i] != tree_list[len_tree_list-i-1]:
                    return False
            return self.left_count == self.right_count
            
        # 递归中序遍历
        def get_list(self,node,n_list):
            if not node:
                return None
            if node.left:
                self.left_count += 1
            if node.right:
                self.right_count += 1
            self.get_list(node.left,n_list)
            n_list.append(node.val)
            self.get_list(node.right,n_list)

## 大神解法 ##

class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def check(node1, node2):
                if not node1 and not node2:
                    return True
                elif not node1 or not node2:
                    return False
                
                if node1.val != node2.val:
                    return False
                return check(node1.left, node2.right) and check(node1.right, node2.left)
            
            return check(root, root)

## 迭代解法 ##

def isSymmetric1(root: TreeNode) -> bool:
        # 如果root节点为空, 或则单个root节点, 则返回True
        if not root or (not root.left and not root.right):
            return True
        # 如果left和right只有一个节点为空, 则返回False
        if not (root.left and root.right):
            return False
        left = [root.left]
        right = [root.right]
        while left:
            leftNode = left.pop()
            rightNode = right.pop()
            
            # 如果节点不相等, 则返回False
            if leftNode.val != rightNode.val:
                return False
            
            # 将左子树的左节点和右子树的右节点写入left/right数组中
            if leftNode.left and rightNode.right:
                left.append(leftNode.left)
                right.append(rightNode.right)
            elif leftNode.left or rightNode.right:
                return False
            
            # 将左子树的右节点和右子树的左节点写入left/right数组中
            if leftNode.right and rightNode.left:
                left.append(leftNode.right)
                right.append(rightNode.left)
            elif leftNode.right or rightNode.left:
                return False
            
        return True

## 简化的迭代 ##

> 链接：https://leetcode-cn.com/problems/symmetric-tree/solution/python3-dui-cheng-er-cha-shu-by-leicj/

from collections import deque
    def isSymmetric2(root: TreeNode) -> bool:
        deq = deque([root, root])
        while deq:
            t1, t2 = deq.pop(), deq.pop()
            # 两个节点都为空, 则继续判断
            if not t1 and not t2: continue
            # 存在一个节点为空, 则为False
            if not(t1 and t2): return False
            if t1.val != t2.val: return False
            # t1, t2的左右节点, 要对称的写入双端队列中
            deq.append(t1.left)
            deq.append(t2.right)
            deq.append(t1.right)
            deq.append(t2.left)
            
        return True

# 104 二叉树的最大深度 #

## 描述 ##

给定一个二叉树，找出其最大深度。  
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。  
说明: 叶子节点是指没有子节点的节点。

示例：  
给定二叉树 \[3,9,20,null,null,15,7\]，  
3  
/ \\  
9 20  
/ \\  
15 7  
返回它的最大深度 3 。

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if root is None: 
                return 0 
            else: 
                left_height = self.maxDepth(root.left) 
                right_height = self.maxDepth(root.right) 
                return max(left_height, right_height) + 1

## 迭代法 ##

> https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/

class Solution:
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """ 
            stack = []
            if root is not None:
                stack.append((1, root))
            
            depth = 0
            while stack != []:
                current_depth, root = stack.pop()
                if root is not None:
                    depth = max(depth, current_depth)
                    stack.append((current_depth + 1, root.left))
                    stack.append((current_depth + 1, root.right))
            
            return depth

# 107 二叉树的层次遍历 II #

## 描述 ##

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：  
给定二叉树 \[3,9,20,null,null,15,7\],  
3  
/ \\  
9 20  
/ \\  
15 7  
返回其自底向上的层次遍历为：  
\[  
\[15,7\],  
\[9,20\],  
\[3\]  
\]

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
            if root is None:
                return []
            p = [root]
            results = []
            current_level_num = 1
            next_level_num = 0
            d = []
            while p:
                current = p.pop(0)
                d.append(current.val)
                current_level_num -= 1
                if current.left:
                    p.append(current.left)
                    next_level_num += 1
                if current.right:
                    p.append(current.right)
                    next_level_num += 1
                if current_level_num == 0:
                    current_level_num = next_level_num
                    next_level_num = 0
                    results.append(d)
                    d = []
            return results[::-1]

## \# 大神代码 ##

> https://leetcode-cn.com/u/user8831v/

class Solution(object): 
        def levelOrderBottom(self, root): 
            """ 
            :type root: TreeNode :rtype: List[List[int]] 
            """ 
            if root == None: return []
            stack = [root]
            res = []
            
            while len(stack) != 0:
                tmp = []
                res_each = []
                for i in stack:
                    res_each.append(i.val)
                    if i.left != None:
                        tmp.append(i.left)
                    if i.right != None:
                        tmp.append(i.right)
                stack = tmp
                res.insert(0,res_each)
                
            return res

## 大佬详细代码 ##

> 作者：yi-xi-4  
> 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/solution/python3-dui-lie-shi-xian-by-yi-xi-4/

class Solution:
        def levelOrderBottom(self, root):
            queue = []                                                  # 结果列表
            cur = [root]                                                # 接下来要循环的当前层节点，存的是节点
            while cur:                                                  # 当前层存在结点时
                cur_layer_val = []                                      # 初始化当前层结果列表为空，存的是val
                next_layer_node = []                                    # 初始化下一层结点列表为空
                for node in cur:                                        # 遍历当前层的每一个结点
                    if node:                                            # 如果该结点不为空，则进行记录
                        cur_layer_val.append(node.val)                  # 将该结点的值加入当前层结果列表的末尾
                        next_layer_node.extend([node.left, node.right]) # 将该结点的左右孩子结点加入到下一层结点列表
                if cur_layer_val:                                       # 只要当前层结果列表不为空
                    queue.insert(0, cur_layer_val)                      # 则把当前层结果列表插入到队列首端
                cur = next_layer_node                                   # 下一层的结点变成当前层，接着循环
            return queue                                                # 返回结果队列

# 108 将有序数组转换为二叉搜索树 #

## 描述 ##

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。  
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:  
给定有序数组: \[-10,-3,0,5,9\],  
一个可能的答案是：\[0,-3,9,-10,null,5\]，它可以表示下面这个高度平衡二叉搜索树：  
0  
/ \\  
\-3 9  
/ /  
\-10 5

## 大神代码1-递归 ##

> 作者：chencyudel  
> https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/dfsdi-gui-er-fen-fa-by-chencyudel/

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
            if nums is None:
                return None
            begin = 0
            end = len(nums) - 1
            if begin > end:
                return None
            mid = (begin + end) >> 1
            root = TreeNode(nums[mid])
            root.left = self.sortedArrayToBST(nums[begin:mid])
            root.right = self.sortedArrayToBST(nums[mid+1:end+1])
            return root

## 大神代码2-递归 ##

> 作者：jia-zhi-tong-1  
> 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/di-gui-by-jia-zhi-tong-1/

class Solution:
        def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
            def construct(start, end):
                middle = (start + end) >> 1
                p = TreeNode(nums[middle])
                if middle > start:
                    p.left = construct(start, middle-1)
                if middle < end:
                    p.right = construct(middle+1, end)
                return p
            
            if not nums:
                return None
            n = len(nums)
            return construct(0, n-1)

# 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 。

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def maxDepth(self,root):
            if root is None: 
                return 0 
            else: 
                left_height = self.maxDepth(root.left) 
                right_height = self.maxDepth(root.right) 
                return max(left_height, right_height) + 1
                
        def isBalanced(self, root: TreeNode) -> bool:
            if root is None: 
                return True
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
    
            if abs(right_height-left_height) > 1:
                return False
            return self.isBalanced(root.left) and self.isBalanced(root.right)

## 大神代码 ##

> 作者：jyd  
> 链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/balanced-binary-tree-di-gui-fang-fa-by-jin40789108/

class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            return self.depth(root) != -1
    
        def depth(self, root):
            if not root: return 0
            left = self.depth(root.left)
            if left == -1: return -1
            right = self.depth(root.right)
            if right == -1: return -1
            return max(left, right) + 1 if abs(left - right) < 2 else -1

class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            if not root: return True
            return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
                self.isBalanced(root.left) and self.isBalanced(root.right)
    
        def depth(self, root):
            if not root: return 0
            return max(self.depth(root.left), self.depth(root.right)) + 1

# 111 二叉树的最小深度 #

## 描述 ##

给定一个二叉树，找出其最小深度。  
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。  
说明: 叶子节点是指没有子节点的节点。

示例:  
给定二叉树 \[3,9,20,null,null,15,7\],  
3  
/ \\  
9 20  
/ \\  
15 7  
返回它的最小深度 2.

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    # https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/di-gui-fa-yan-du-you-xian-sou-suo-python-by-juncao/
    class Solution:
        def minDepth(self, root: TreeNode) -> int:
            if root is None: 
                return 0
            elif not root.left:
                return self.minDepth(root.right) + 1
            elif not root.right:
                return self.minDepth(root.left) + 1
            else:
                left_height = self.minDepth(root.left) 
                right_height = self.minDepth(root.right) 
                return min(left_height, right_height) + 1

## 大神解法BFS ##

> 作者：baiyizhe  
> 链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/fei-di-gui-bfshe-dfs-by-baiyizhe/

class Solution:
        def minDepth(self, root: TreeNode) -> int:
            if not root: return 0
            queue = [(1, root)]
            while queue:
                depth, node = queue.pop(0)
                if not node.left and not node.right:
                    return depth
                if node.left:
                    queue.append((depth + 1, node.left))
                if node.right:
                    queue.append((depth + 1, node.right))

## 其它解法 ##

> https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode/

# 112 路径总和 #

## 描述 ##

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

示例:  
给定如下二叉树，以及目标和 sum = 22，  
5  
/ \\  
4 8  
/ / \\  
11 13 4  
/ \\ \\  
7 2 1  
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

## 代码 ##

# https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode/
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def hasPathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: bool
            """
            if not root:
                return False
    
            sum -= root.val
            if not root.left and not root.right:  # if reach a leaf
                return sum == 0
            return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

## 大佬迭代方法 ##

class Solution:
        def hasPathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: bool
            """
            if not root:
                return False
    
            de = [(root, sum - root.val), ]
            while de:
                node, curr_sum = de.pop()
                if not node.left and not node.right and curr_sum == 0:  
                    return True
                if node.right:
                    de.append((node.right, curr_sum - node.right.val))
                if node.left:
                    de.append((node.left, curr_sum - node.left.val))
            return False