LeetCode Cookbook 树（4）

CSDN话题挑战赛第2期
参赛话题：算法题解

LeetCode Cookbook 树（4）

   本节内容主要是一些零散的题目，主要是关于 子树、叶子结点 的问题 。

404. 左叶子之和（model-VIII 叶子）

题目链接：404. 左叶子之和
题目大意：给定二叉树的根节点 root ，返回所有左叶子之和。

例如：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24。
1
2
3

• 解题思路：DFS 与 左叶子结点判断。
• 时间复杂度：$O(N^2)$ N为二叉树的结点数
• 空间复杂度：$O(N)$

# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        if root.left and root.left.left is None and root.left.right is None:
            return root.left.val+self.sumOfLeftLeaves(root.right)
        ans = 0
        return self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13

508. 出现次数最多的子树元素和（model-VIII 叶子）

题目链接：508. 出现次数最多的子树元素和
题目大意：给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

例如：

输入: root = [5,2,-3]
输出: [2,-3,4]
1
2

输入: root = [5,2,-5]
输出: [2]
1
2

解题思路： DFS 进行子树和的计算 记住 如何跳出 Counter 计数器的个部分组成。

• 时间复杂度：$O(N)$ N为二叉树结点数
• 空间复杂度：$O(N)$

# 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 findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        # 一直没看树了 快忘干净了
        # 计数器的使用方法 主要 .items() 与 .values()
        cnt = Counter()# make a counter
        # 递归深度变换 比栈简单多了
        def dfs(root: TreeNode) -> int:
            if root is None:
                return 0
            sum = dfs(root.left) + dfs(root.right) + root.val
            cnt[sum] += 1
            return sum
        # 一定要套在所解决的根上
        dfs(root)
        maxCnt = max(cnt.values())
        # 取出次数为maxCnt的全部数据
        return [s for s,c in cnt.items() if c == maxCnt]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

572. 另一棵树的子树（model-VIII 子树+model-IV 同树判断）

题目链接：572. 另一棵树的子树
题目大意：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

例如：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
1
2

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
1
2

• 解题思路： DFS + 同树判断 Model-IV
• 时间复杂度：$O(P\ast Q)$ P、Q分别为二叉树p、q的结点数。
• 空间复杂度：$O(max(H_p,H_q))$ H为树的高度。

# 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 isSubtree(self, p: TreeNode, q: TreeNode) -> bool:

        def isSame(s: TreeNode,t: TreeNode) -> bool:
            if s is None and t is None: return True
            if s and t:
                if s.val != t.val:
                    return False
                return isSame(s.left,t.left) and isSame(s.right,t.right)
            return False 
            
        if isSame(p,q):
            return True
        if p is None: return False
        if self.isSubtree(p.left,q) or self.isSubtree(p.right,q):
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

872. 叶子相似的树（model-VIII 叶子）

题目链接：872. 叶子相似的树
题目大意：请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

例如：

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true
1
2

输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false
1
2

• 解题思路： 收集两棵树的叶子结点 作比较 。
• 时间复杂度：$O(N_1+N_2)$ $N_1,N_2$ 分别为两颗二叉树的结点数
• 空间复杂度：$O(N_1+N_2)$

# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        
        res = list()
        def dfs(node:Optional[TreeNode],res: List[int]) -> None:
            if node is None: return
            if node.left is None and node.right is None:
                res.append(node.val)
            dfs(node.left,res)
            dfs(node.right,res)
        
        res1,res2 = list(),list()
        dfs(root1,res1)
        dfs(root2,res2)
        return res1 == res2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

897. 递增顺序搜索树（model-VI 二叉搜索树）

题目链接：897. 递增顺序搜索树
题目大意：给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

例如：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
1
2

• 解题思路： 区别于 114. 二叉树展开为链表 这用到的是 二叉搜索树 中序遍历后得到的便是一个升序序列 我的代码中用到了 pop() 函数 所有对 res 数组进行了倒序。
• 时间复杂度：$O(N)$ N为二叉搜索树的结点数
• 空间复杂度：$O(N)$

# 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 increasingBST(self, root: TreeNode) -> TreeNode:
        
        def inOrder(node: TreeNode) -> None:
            if node is None: return 
            inOrder(node.left)
            res.append(node.val)
            inOrder(node.right)
        
        res = list()
        inOrder(root)
        res = res[::-1]
        root = TreeNode(res.pop())
        node = root
        while res:
            tree = TreeNode(res.pop())
            node.left = None
            node.right = tree
            node = node.right
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

993. 二叉树的堂兄弟节点（model-VIII 叶子）

题目链接：993. 二叉树的堂兄弟节点
题目大意：在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

例如：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false
1
2

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
1
2

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false
1
2

• 解题思路： DFS遍历 各结点的深度和父结点
• 时间复杂度：$O(N)$ N为二叉树的结点数
• 空间复杂度：$O(N)$

# 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 isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        # 
        xa,xb,xc = None,None,False
        ya,yb,yc = None,None,False

        def dfs(node: Optional[TreeNode],depth: int,parent: Optional[TreeNode]):
            if node is None: return 
            nonlocal xa,xb,xc,ya,yb,yc 
            if node.val == x:
                xa,xb,xc = depth,parent,True
            if node.val == y:
                ya,yb,yc = depth,parent,True
            
            # 找到就撤
            if xc and yc: return
            dfs(node.left,depth+1,node)
            if xc and yc: return 
            dfs(node.right,depth+1,node)

        dfs(root,0,None)
        return xa==ya and xb != yb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

513. 找树左下角的值（model-VIII 叶子）

题目链接： 513. 找树左下角的值
题目大意：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

例如：

输入: root = [2,1,3]
输出: 1

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
1
2
3
4
5

• 解题思路：BFS 非常简单
• 时间复杂度：$O(N)$ N为二叉树的结点数
• 空间复杂度：$O(N)$

# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
            ans = node.val
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

337. 打家劫舍 III（model-VIII 扩展 动态取树）

题目链接：337. 打家劫舍 III
题目大意：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

例如：

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
1
2
3

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
1
2
3

• 解题思路： DFS + 动态规划
• 时间复杂度：$O(N)$ N为树的结点数 后序遍历N
• 空间复杂度：$O(N)$

# 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 rob(self, root: Optional[TreeNode]) -> int:

        def _rob(node: Optional[TreeNode]) -> int:
            # 不 rob
            if node is None: return 0,0
            L = _rob(node.left)
            R = _rob(node.right)
            # rob 取当前结点 左右子树不取
            v1 = node.val + L[1] + R[1]
            # not rob 不取当前结点 分别取左右子树中最大的值
            v2 = max(L) + max(R)
            return v1,v2
        
        return max(_rob(root))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1028. 从先序遍历还原二叉树（model-VIII 扩展）

题目链接：1028. 从先序遍历还原二叉树
题目大意：我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。

例如：

输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]
1
2

输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]
1
2

输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]
1
2

• 解题思路： 注意观察 字符串的规律 进行建树。
• 时间复杂度：$O(N)$ N为字符串 t 的长度
• 空间复杂度：$O(H)$ H为二叉树的高度

# 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 recoverFromPreorder(self, t: str) -> Optional[TreeNode]:
        stack,idx = list(),0
        n = len(t)
        while idx < n:
            level,val = 0,""
            # '-' 的个数代表结点的深度
            while idx<n and t[idx] == '-':
                level += 1
                idx += 1
            
            # 存数字
            while idx<n and t[idx].isdigit():
                val += t[idx]
                idx += 1
            
            # 确保当前结点所处的level 与 节点深度一致
            while len(stack) > level:
                stack.pop()
            
            # 构建子结点 左右顺序
            node = TreeNode(int(val))
            if stack and stack[-1].left is None:
                stack[-1].left = node
            elif stack and stack[-1].right is None:
                stack[-1].right = node
            # 不同的 level 放在对应的 stack 索引中
            stack.append(node)

        return stack[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1026. 节点与其祖先之间的最大差值（model-VIII 扩展）

题目链接：1026. 节点与其祖先之间的最大差值
题目大意：给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

例如：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
1
2
3
4
5
6
7
8
9

• 解题思路： DFS 找最大值与最小值
• 时间复杂度：$O(N)$ N为二叉树的结点数 前序遍历
• 空间复杂度：$O(H)$ H为树的高度

# 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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        if root is None: return 0
        self.ans = 0
        self.dfs(root,root.val,root.val)
        return self.ans
    
    def dfs(self,node: Optional[TreeNode],hi: int,lo: int) -> None:
        self.ans = max(self.ans,hi-lo)
        if node:
            hi,lo = max(hi,node.val),min(lo,node.val)
            self.dfs(node.left,hi,lo)
            self.dfs(node.right,hi,lo)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

   努力 奋斗！ 这部分题目比较难一些，主要是 需要结合其他的数据结构或一些技巧进行解题，但DFS仍然是非常强大的，不过，审题仍然是最重要的一项，如果审题后确定 DFS不适合，而BFS更适合，需要理性选取最易于编写的有利代码。