leetcode - 递归

快来打我* 2022-03-07 00:38 189阅读 0赞

**目录**

98.验证搜索二叉树

22.括号生成

100.相同的树

101.对称二叉树

104.树的最大深度

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

110.平衡二叉树

111.二叉树的最小深度

112.路径总和

226.翻转二叉树

--------------------

![20200423163419632.PNG][]

### 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
            """
            
            return self.isValid(root, float('-inf'), float('inf'))    #最小值为无限小，最大值为无限大
            
        def isValid(self, root, min, max):
            if not root:
                return True
            
            if root.val <= min or root.val >= max: # 此处不能相等
                return False
            
            return self.isValid(root.left, min, root.val) and self.isValid(root.right, root.val, max)

### 22.括号生成 ###

给出 *n* 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且**有效的**括号组合。

例如，给出 *n* =3，生成结果为：

[
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
    
            if n == 0:
                return []
            
            result = []
            self.helper(n, n, "", result)
            return result 
        
        def helper(self, l, r, item, result):  
            if l > r:
                return     #此行代码要放在前面，如果剩余的左括号大于由括号时，则不满足条件
            
            if l > 0:
                self.helper(l-1, r, item+'(', result)
            if r > 0:
                self.helper(l, r-1, item+ ')', result)
            if l == 0 and r == 0:
                result.append(item)

### 100.相同的树 ###

给定两个二叉树，编写一个函数来检验它们是否相同。

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

**示例 1:**

输入:       1         1
              / \       / \
             2   3     2   3
    
            [1,2,3],   [1,2,3]
    
    输出: true

**示例 2:**

输入:      1          1
              /           \
             2             2
    
            [1,2],     [1,null,2]
    
    输出: false

**示例 3:**

输入:       1         1
              / \       / \
             2   1     1   2
    
            [1,2,1],   [1,1,2]
    
    输出: false

# 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 isSameTree(self, p, q):
            """
            :type p: TreeNode
            :type q: TreeNode
            :rtype: bool
            """
            
            if p is None and q is None: #递归的退出的条件
                return True 
            
            if p is not None and q is not None:
                return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) #需要满足3 个条件，满足2根结点的值是否相等，左右结点是否相等
            else:
                return False

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

**说明:**

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

# 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 isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            
            if root is None: 
                return True 
            
            return self.helper(root.left, root.right)
        
        def helper(self, left, right):
            if left is None and right is None: #退出条件
                return True 
            if left is None or right is None or left.val != right.val: #r如果两者有一项为空，则表明不是对称二叉树
                return False
            
            return self.helper(left.left, right.right) and self.helper(left.right, right.left)

### 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
            """
            if root is None:
                return 0
            else: #返回左右子树中最大的深度
                return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

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

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

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

**示例:**

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

# 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 sortedArrayToBST(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
    
     
            def helper(nums, start, end):
                if start > end: #退出条件
                    return None
                mid = (start + end) // 2
                node = TreeNode(nums[mid])
                
                node.left = helper(nums, start, mid-1)
                node.right = helper(nums, mid+ 1, end)
                
                return node #需要return node出来连接成树
            
            return helper(nums, 0, len(nums)-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(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def isBalanced(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def get_height(root):
                if root is None:
                    return 0 
                left_height = get_height(root.left)
                right_height = get_height(root.right)
                if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1: #如果左子树大于右子树的高度时，返回的left_height 为-1，可以写成left_height ==-1 or right_height ==-1
                    return -1
                else:
                    return max(left_height, right_height) + 1
                
            return (get_height(root) >= 0)

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

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

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

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

**示例:**

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

3
       / \
      9  20
        /  \
       15   7

返回它的最小深度 2.

特殊情况：

3
       / 
      9

此时返回的应该是 2

# 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 minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return 0 
            
            if root.left and root.right:
                return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
            else:
                return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

### 112.路径总和 ###

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

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

**示例:**  
给定如下二叉树，以及目标和 `sum = 22`，

5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1

返回 `true`, 因为存在目标和为 22 的根节点到叶子节点的路径 `5->4->11->2`。

# 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 root is None: #如果树为空，则错
                return False
            
            #更新sum 值，当找到叶子结点就是余下的值时，则返回True
            if root.left is None and root.right is None and root.val == sum:
                return True 
            
            else:
                # 递归寻找左右结点的值
                return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

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

翻转一棵二叉树。

**示例：**

输入：

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

输出：

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

# 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 invertTree(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            if root is not None:
                # 交换左右的结点
                root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root

[20200423163419632.PNG]: /images/20220307/a32a5ee582fc48a29432bb73ef2e102d.png