数据结构-树进阶刷题

二叉树的进阶操作

LeetCode 110. 平衡二叉树

对获取树高的函数进行修改，在获取树高的函数中对平衡进行判断即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.get_help(root) != -1
    
    def get_help(self, root):
        if not root:
            return 0
        left = self.get_help(root.left)
        if left == -1:
            return -1
        right = self.get_help(root.right)
        if right == -1:
            return -1
        if abs(left - right) < 2:
            return max(left, right) + 1
        else:
            return -1

LeetCode 112. 路径总和

递归向下求值，每次减去当前结点的值，递归结束的条件是遇到叶子结点且刚
好求得的值为 0。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        queue = collections.deque()
        queue.append([root, root.val])
        while queue:
            node, num = queue.popleft()
            if not node.left and not node.right  and num == targetSum:
                 return True 
            if node.left:
                queue.append([node.left, num + node.left.val])
            
            if node.right:
                queue.append([node.right, num + node.right.val])
        return False 

LeetCode 105. 从前序与中序遍历序列构造二叉树

递归拆分。前序遍历的第一个结点是根结点，在中序遍历中找到该根结点的位
置，区分出左右子树，再递归向下拆分左右子树即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return 
        root = TreeNode(preorder[0])
        index  = inorder.index(preorder[0]) # 找中序遍历根所在的位置
        root.left  = self.buildTree(preorder[1:index+1], inorder[:index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root
        

LeetCode 222. 完全二叉树的结点个数

递归数左子树和右子树的结点，加上根结点即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

LeetCode 剑指 Offer 54. 二叉搜索树的第 k 大结点

统计右子树的结点个数 cntr，递归处理即可。如果 k = cntr + 1，那么是根
结点，如果 k ≤ cntr，那么在右子树中且是第 k 大，否则在左子树中且是第
k − cntr − 1 大。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root:
            return 
        self.count = 0
        self.data = 0
        def get_help(root):
            if not root:
                return 
            get_help(root.right)
            self.count += 1
            if self.count == k:
                self.data = root.val
                return
            get_help(root.left)
            return 
        get_help(root)
        return self.data

LeetCode 剑指 Offer 26. 树的子结构

先和根结点比较，再递归地和左右子树比较即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def get_help(self, A, B):
        if not B:
            return True 
        if not A:
            return False 
        if A.val != B.val:
            return False
        
        return self.get_help(A.left, B.left) and self.get_help(A.right, B.right)
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        return self.get_help(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

LeetCode 968. 监控二叉树

dp 的第一维表示“父结点”是否放置摄像头，第二维表示“当前结点”是否放
置摄像头。例如 dp[0][0] 表示父结点不放置摄像头，当前结点也不放置摄像头
的情况下，覆盖整棵树所需要的最少摄像头数。
对放置情况进行分情况讨论。以 dp[0][0] 为例，有：

这表示，父节点和当前结点都不放摄像头的情况下，所需要的最少摄像头数，需
要取以下三种情况的最小值：
(1) 左子树的父节点不放置摄像头 + 左子树自身放置摄像头 + 右子树的父节点
不放置摄像头 + 右子树自身不放置摄像头
(2) 左子树的父节点不放置摄像头 + 左子树自身不放置摄像头 + 右子树的父节
点不放置摄像头 + 右子树自身放置摄像头
(3) 左子树的父节点不放置摄像头 + 左子树

LeetCode 662. 二叉树最大宽度

按照完美二叉树的形式，对所有的结点进行编号。层序遍历后同一层内编号最
大结点和最小编号结点的编号之差加一即为所求。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 
        result = []
        item = []
        queue = collections.deque()
        queue.append([root, 1])
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node, index = queue.popleft()
                tmp.append(index)
                if node.left:
                    queue.append([node.left, index *2 ])
                if node.right:
                    queue.append([node.right,index *2 + 1])
            result.append(tmp)
        for res in result:
            item.append(res[-1] - res[0] + 1)
        return max(item)