二叉树类题目 力扣

像上文提到的树的介绍与应用，这篇文章我们再多尝试几个例子。

226. 翻转二叉树

解题思路：

像我们上文提到的，遇到树的题目，先看看题目是不是能直接用遍历的方式解决呢？

其实使用前序遍历的方式，逐层颠倒左右子树就可以。

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:return 
        self.traverse(root)
        return root
    
    def traverse(self, root):
        if not root:return

        tmp = root.left
        root.left = root.right
        root.right = tmp

        self.traverse(root.left)
        self.traverse(root.right) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

能不能用分解的方式呢？

分解的方式有两种，分别对应先序遍历和后续遍历。

分解的方式一般是利用递归调用函数自身，进而处理每一层的子节点。

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
    if not root:return 
	
	root.left, root.right = root.right, root.left # 先序
	
    self.invertTree(root.left)
    self.invertTree(root.right)
    
    return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
    if not root:return 
    self.invertTree(root.left)
    self.invertTree(root.right)

    root.left, root.right = root.right, root.left # 后序
    return root
1
2
3
4
5
6
7
8
9
10
11
12
13

以上的递归方式也是 DFS 的体现，让我们看一下 BFS 的方法。

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        
        if not root:return 
        queue = [root]
        while queue:
            tmp = queue.pop(0)
            tmp.left, tmp.right = tmp.right, tmp.left

            if tmp.left:
                queue.append(tmp.left)
            if tmp.right:
                queue.append(tmp.right)

        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

116. 填充每个节点的下一个右侧节点指针

解题思路：

这道也能直接使用遍历的方式解决，但注意一点：

像上一题的先序遍历如下，

这里遵循二分的思想，分别遍历左右子树，所以不能把最下层不同父节点，的子节点相连接。

也就是题目例子中的 5 不能指向 6。

	
	pass		# 先序位置
	
    self.invertTree(root.left)
    self.invertTree(root.right)
1
2
3
4
5

我们只要增加一行递归就能解决。

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':

        if not root:
            return None
        
        self.traverse(root.left, root.right)
        return root

    def traverse(self, node1, node2):
        if not node1 or not node2:
            return

        node1.next = node2 # 左面的节点指向右面的

        self.traverse(node1.left, node1.right)
        self.traverse(node1.right, node2.left) # 增加不同父节点的连接
        self.traverse(node2.left, node2.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

114. 二叉树展开为链表

题目希望我们在原地把二叉树拉平成链表。

所以使用前序遍历的方式直接遍历，构造一条链表就违背了题意。

所以这道题使用分解的方式，利用递归原地拉平链表。

具体细节如下注释，可以多看几遍。

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        if not root:
            return
            
		
        self.flatten(root.left)
        self.flatten(root.right)

        #1.后序遍历位置，分解问题往往是由下往上的处理子问题
        # 利用题目的例子，我们以根节点左子树为例 2->3->4
        #记录当前节点左右子树
        left = root.left #此时 3 为 left，来自 （2.left->3）
        right = root.right #4 为 right, 来自 （2.right->4）

        #2.将左子树作为右子树，左子树设为 None, 先不处理刚刚记录的右子树的值 
        root.right = left #2.right->3
        root.left = None #2.left->null
		
		#3. 将原来的右子树（right）接到现在的右子树上（2.right->3）
        p = root #当前的节点是 2
        while(p.right is not None): # 2->3 
            p = p.right  # 如果不遍历到节点3，节点 3 会丢失
        p.right = right  #4
                        #2.right->3->4
		#以上是以根节点 1 的左子树为例，依照递归的顺序，根节点的右子树处理如上。
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