Leetcode-二叉树
二叉树的一些思想
- 前序遍历(preOrder) root->left->right
- 中序遍历(inOrder) left-> root->right 二叉搜索树中，其遍历结果为有序数组
- 后序遍历(postOrder) left->right->root
- 广度优先搜索(BFS)
- 深度优先搜索(DFS)
- 递归(Recursion)，根据要求选择使用前序，中序，后序的递归框架来解决问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def increasingBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
if not root: return
dfs(root.left)
root.left = None
self.cur.right = root
self.cur = root
dfs(root.right)
res = self.cur = TreeNode(None)
dfs(root)
return res.right
|
1
2
3
4
5
6
7
8
9
10
| def invertTree(self, root):
if not root: return None
root.left,root.right = root.right,root.left
root.left = self.invertTree(root.left)
root.right = self.invertTree(root.right)
return root
|
1
2
3
4
5
6
7
8
9
10
| def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not (t1 and t2):
return t1 if t1 else t2
t1.val+=t2.val
t1.left = self.mergeTrees(t1.left,t2.left)
t1.right = self.mergeTrees(t1.right,t2.right)
return t1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
self.res = 0
def dfs(root,L,R):
if not root: return
if L<= root.val <=R:
self.res+=root.val
dfs(root.left,L,R)
dfs(root.right,L,R)
dfs(root,L,R)
return self.res
|
1
2
3
4
5
| def maxDepth(self, root: TreeNode) -> int:
if not root:return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right)) +1
|
1
2
3
4
5
6
7
8
9
10
11
| def postorder(self, root: 'Node') -> List[int]:
self.res = []
def helper(root):
if not root:return
for child in root.children:
helper(child)
self.res.append(root.val)
helper(root)
return self.res
|
1
2
3
4
5
6
7
8
9
10
| def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:return
if root.val == val:
return root
if root.val < val:
return self.searchBST(root.right,val)
else:
return self.searchBST(root.left,val)
|
1
2
3
4
5
6
7
8
9
10
| def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) == 0 : return
mid = len(nums)//2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| def increasingBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
if not root: return
dfs(root.left)
root.left = None
self.cur.right = root
self.cur = root
dfs(root.right)
res = self.cur = TreeNode(None)
dfs(root)
return res.right
|
1
2
3
4
| def maxDepth(self, root: 'Node') -> int:
if not root:return 0
return max([self.maxDepth(i) for i in root.children]+[0])+1
|
1
2
3
4
5
6
7
8
9
10
11
12
| def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or p == root or q == root: return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if not left and not right: return
elif not left: return right
elif not right:return left
else: return root
|