Leetcode刷题记录——二叉树修改与构造篇
Leetcode226 翻转二叉树
只要能遍历每个节点，然后改变左右子树的遍历方式都可以做到
本题采用的是层序遍历
Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
queue = deque()
queue.append(root)
while queue:
for _ in range(len(queue)):
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
|
Leetcode106 从中序与后序遍历序列构造二叉树
给定一个二叉树的中序遍历数组和后序遍历数组，来还原一颗二叉树，理论部分很简单
先后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组
一层一层切下去，每次后序数组最后一个元素就是当前子树根节点元素
说到一层一层切割，就应该想到了递归
来看一下一共分几步：
- 第一步：如果数组大小为零的话，说明是空节点了。
- 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
- 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间
Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
idx = inorder.index(root_val)
inorder_left = inorder[:idx]
inorder_right = inorder[idx+1:]
postorder_left = postorder[:len(inorder_left)]
postorder_right = postorder[len(inorder_left):len(postorder)-1]
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root
|
Leetcode654 最大二叉树
构造一棵二叉树时，考虑用前序遍历的方式，先构造中间节点，再去递归地构造左子树和右子树
还是递归三部曲：
1、确定递归函数的参数和返回值
参数传入的是存放元素的数组，返回该数组构造的二叉树的根结点
2、确定终止条件
题目中说了输入的数组大小一定是大于等于1的，所以不用考虑小于1的情况
当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点
然后返回这个节点，这表示一个数组大小是1的时候，构造了一个新的节点，并返回
3、确定单层递归的逻辑
有三步：
1、先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组
2、最大值所在的下标左区间 构造左子树
3、最大值所在的下标右区间 构造右子树
Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 1:
return TreeNode(nums[0])
max_val = max(nums)
index = nums.index(max_val)
node = TreeNode(max_val)
if index > 0:
nums_left = nums[:index]
node.left = self.constructMaximumBinaryTree(nums_left)
if index < len(nums) - 1:
nums_right = nums[index+1:]
node.right = self.constructMaximumBinaryTree(nums_right)
return node
|
Leetcode617 合并二叉树
还是递归三部曲：
1、确定递归函数的参数和返回值
首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点
2、确定终止条件：
因为是传入了两个树，那么就有两个树遍历的节点root1和 root2，如果root1== NULL 了，两个树合并就应该是 root2了（如果root2也为NULL也无所谓，合并之后就是NULL）
反过来如果root2== NULL，那么两个数合并就是root1（如果root1也为NULL也无所谓，合并之后就是NULL）
3、确定单层递归的逻辑
单层递归的逻辑比较简单，就要把两棵树的元素加到一起
Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
if not root1 and not root2:
return None
val = root1.val + root2.val
node = TreeNode(val)
node.left = self.mergeTrees(root1.left, root2.left)
node.right = self.mergeTrees(root1.right, root2.right)
return node
|