二刷 leetcode (10)

桃扇骨 2022-05-20 05:53 154阅读 0赞

104. 二叉树的最大深度

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

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

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

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

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

代码：递归找出左右子树的最大深度

# 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 maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            #### the first method
            if root is not None:
                return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
            else:
                return 0
            
            
            #### the second method
            if root is None:
                return 0
            leftDepth=self.maxDepth(root.left)+1
            rightDepth=self.maxDepth(root.right)+1
            return max(leftDepth,rightDepth)

98. 验证二叉搜索树

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

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

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

示例 1:

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

示例 2:

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

代码：

# 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 isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            ### the first method
            def boolean_SearchTree(root, min, max):
                if root == None:
                    return True
                if root.val <= min or root.val >=max:
                    return False
                return boolean_SearchTree(root.left, min, root.val) and boolean_SearchTree(root.right, root.val, max)
            return boolean_SearchTree(root, -2**63, 2**63-1)
            
            #### the second method
            def inorderTraversal(root, inorder):
                if root:
                    inorderTraversal(root.left, inorder)
                    inorder.append(root.val)
                    inorderTraversal(root.right, inorder)
            
            if root is None:
                return True
            inorder = []
            inorderTraversal(root, inorder)
            for i in range(len(inorder) - 1):
                if inorder[i] >= inorder[i+1]:
                    return False
            return True
            
        
            #### 非递归方法
            stack = [] 
            pre = None
            while stack or root:
                while root:
                    stack.append(root)
                    root = root.left
                if root:
                    node = stack.pop()
                    if pre ==None or node.val > pre.val:
                        pre = node
                    else:
                        if node.val <= pre.val:
                            return False
                    root = root.right
            return True

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 Solution2(object):
        """
        两种辅助函数
        """
        def recursive(self, left, right):
            if left is None and right is None:
                return  True
            if left is None or right is None:
                return False
            if left.val == right.val:
                return self.recursive(left.left, right.right) and self.recursive(left.right, right.left)
            return False
    
        def Help(self, L, R):
            if not L and not R:
                return True
            elif L and R and L.val == R.val:
                return self.Help(L.left, R.right) and self.Help(L.right, R.left)
            else:
                return False
    
    
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if root is None:
                return True
            else:
                return self.recursive(root.left, root.right)

102. 二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:  
给定二叉树: `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

代码：

class Solution3:
        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
    
            #### the first method
    
            # if root is None:
            #     return []
            # res = []
            # queue = [root]
            # while queue:
            #     nodes = []
            #     values = []
            #     for node in queue:
            #         if node.left:
            #             nodes.append(node.left)
            #         if node.right:
            #             nodes.append(node.right)
            #         values += [node.val]
            #     res += [values]
            #     queue = nodes
            # return res
    
            #### the second method
            res = []
            if root is None:
                return res
            res.append([root.val])
            queue = [root]
            while queue and queue[0]:
                level = []
                count = len(level)
                for i in range(count):
                    node = queue.pop(0)
                    if node.left:
                        queue.append([root.left])
                        level.append(node.left.val)
                    if node.right:
                        queue.append([root.right])
                        level.append(node.right.val)
                if level:
                    res.append(level)
            return res

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1。

示例:

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

代码：

class Solution4(object):
        def sortedArrayToBST(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            ### the first method
            if len(nums) == 0:
                return None
            mid = len(nums) // 2
            root = TreeNode(nums[mid])
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid+1 :])
            return root
    
            #### the second method 
            if not nums:
                return None
    
            def insert(nums, l, r):
                if l > r:
                    return None
                m = (l + r) // 2
                newNode = TreeNode(nums[m])
                newNode.left = insert(nums, l, m - 1)
                newNode.right = insert(nums, m + 1, r)
                return newNode
    
            return insert(nums, 0, len(nums) - 1)

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

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

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。