编程能力提升_4

迈不过友情╰ 2022-03-02 05:05 192阅读 0赞

**目录**

1.给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

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

3.给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。返回 \[0, 1, ..., N\] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：如果 S\[i\] == "I"，那么 A\[i\] < A\[i+1\]如果 S\[i\] == "D"，那么 A\[i\] > A\[i+1\]

4.给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

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

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

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

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

### 1.给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 ###

**示例 1:**

输入:      1          1
              /           \
             2             2
    
            [1,2],     [1,null,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:
        def isSameTree(self, p, q):
            """
            :type p: TreeNode
            :type q: TreeNode
            :rtype: bool
            """
            if not p and not q:
                return True
            elif p is not None and q is not None:
                if p.val == q.val:
                    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
                else:
                    return False
            else:
                return False

方法二：

class Solution(object):
        def isSameTree(self, p, q):
            Listp=self.getList(q,[])
            Listq=self.getList(p,[])
            if Listp==Listq:
                return True
            else:
                return False
            
        def getList(self,tree,List):
            if not tree:
                List.append(None)
                return List
            List.append(tree.val)
            List=self.getList(tree.left,List)
            List=self.getList(tree.right,List)
            return List

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

例如，二叉树 `[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:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def isSymmetric(self, root: TreeNode) -> bool:
            def isSame(p,q):
                #都为非空，但是值相等（再次进入递归）
                if p and q and p.val==q.val:
                    return isSame(p.left,q.right) and isSame(p.right,q.left)
                #两个节点都为空,返回真
                if not p and not q:
                    return True
                #其他情况返回假
                return False
            
            if not root:
                return True
            return isSame(root.left,root.right)

### 3.给定只含 `"I"`（增大）或 `"D"`（减小）的字符串 `S` ，令 `N = S.length`。返回 `[0, 1, ..., N]` 的任意排列 `A` 使得对于所有 `i = 0, ..., N-1`，都有：如果 `S[i] == "I"`，那么 `A[i] < A[i+1]如果 S[i] == "D"，那么 A[i] > A[i+1]` ###

**示例 1：**

输出："IDID"
    输出：[0,4,1,3,2]

class Solution:
        def diStringMatch(self, S):
            """
            :type S: str
            :rtype: List[int]
            """
            left = 0
            right = len(S)
            A = []
            for i in S:
                #如果是I，因为它的右侧数据要比他大，所以当前位置
                #的数据选择最小的数
                if i == 'I':
                    A.append(left)
                    left += 1
                #如果是D，因为右侧要比他小，所以选择当前最大的数
                else:
                    A.append(right)
                    right -= 1
            #最后的一个数据加入
            A.append(right)
            return A

### 4.给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 ###

**示例：**  
给定二叉树 `[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
            
            lf = self.maxDepth(root.left)+1
            rt = self.maxDepth(root.right)+1
            
            return max(lf,rt)

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

本题中，一个高度平衡二叉树是指一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 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
    
    #利用递归的思想，取中间的数为root，左边的全是左子树，右边的全是右子树
    class Solution(object):
        def sortedArrayToBST(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            if not nums:
                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

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

**示例 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` 。

class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            if not root:
                return True
            if abs(self.countfloor(root.left)-self.countfloor(root.right))>1:
                return False
            else:
                return self.isBalanced(root.left) and self.isBalanced(root.right)
        
        
        def countfloor(self,root):  #求二叉树及其子树的高度
            if not root:
                return 0
            else:
                return max(self.countfloor(root.left),self.countfloor(root.right))+1

### 7.给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 ###

**示例:**

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

3
       / \
      9  20
        /  \
       15   7

返回它的最小深度 2.

class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root:
                if root.left and root.right:
                    return 1+min(self.minDepth(root.left),self.minDepth(root.right))
                #下面语句是在求树实际的最小深度，因为上一语句在判断时，需要其深度
                elif root.left:
                    return 1+self.minDepth(root.left)
                elif root.right:
                    return 1+self.minDepth(root.right)
                else:
                    return 1
            else:
                return 0

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

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

**示例:**  
给定如下二叉树，以及目标和 `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:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def hasPathSum(self, root: TreeNode, sum: int) -> bool:
            if not root:
                return False
            if not root.left and not root.right:
                return root.val^sum==0
    
            return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)