- 思路
- example
- 利用二叉搜索树性质（排序）
- 注意条件：
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
- 递归，自上而下 （更接近前序遍历）
- 四种情况：
- 当前节点val 等于p,q其中一个, return 当前节点
- 当前节点val 在q,q对应值之间, return 当前节点
- 当前节点val > p,q值，在左子树搜索 （递归）
- 当前节点val < p,q值，在右子树搜索 （递归）
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > q.val:
p, q = q, p
# p.val < q.val
if root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if root.val < p.val:
return self.lowestCommonAncestor(root.right, p, q)
# otherwise
return root
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traversal(root):
if root.val == p.val or root.val == q.val:
return root
if p.val < root.val < q.val or q.val < root.val < p.val:
return root
if p.val < root.val and q.val < root.val:
return traversal(root.left)
if p.val > root.val and q.val > root.val:
return traversal(root.right)
return traversal(root)
- 迭代, 排序结构适合用迭代
- 遍历cur，每次通过比大小来决定方向(cur = cur.left 或者 cur = cur.right)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur = root
while cur:
if cur.val > p.val and cur.val > q.val:
cur = cur.left
elif cur.val < p.val and cur.val < q.val:
cur = cur.right
else:
break
return cur
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if q.val < p.val:
p, q = q, p
cur = root
while cur:
if cur == p or cur == q:
return cur
if cur.val < p.val:
cur = cur.right
elif cur.val > q.val:
cur = cur.left
else:
return cur
- 思路
- example
- 搜索遇空节点即是插入位置。
- 递归 (无返回值)
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
def traversal(root):
nonlocal parent
if root == None:
node = TreeNode(val)
if parent.val < val:
parent.right = node
else: # >
parent.left = node
return
parent = root
if root.val < val:
traversal(root.right)
else:
traversal(root.left)
return
if root == None:
return TreeNode(val)
parent = None
traversal(root)
return root
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
def traversal(root):
if root == None:
return TreeNode(val)
if root.val > val:
root.left = traversal(root.left)
if root.val < val:
root.right = traversal(root.right)
return root
return traversal(root)
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root == None:
return TreeNode(val, None, None)
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
cur = root
parent, child_type = None, 'left'
while cur:
parent = cur
if cur.val > val:
cur = cur.left
child_type = 'left'
else:
cur = cur.right
child_type = 'right'
node = TreeNode(val)
if parent == None:
return node
if child_type == 'left':
parent.left = node
else:
parent.right = node
return root
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root == None:
return TreeNode(val)
cur = root
while cur:
if cur.val < val:
if cur.right:
cur = cur.right
else:
cur.right = TreeNode(val)
return root
elif cur.val > val:
if cur.left:
cur = cur.left
else:
cur.left = TreeNode(val)
return root
- 思路
- example
- 注意树中可能不包含需要删除的节点
- 递归，返回值：以当前节点为根节点并且已删除所要求节点的树。
- 当前节点为删除节点
- 左子树加到 右子树最小值 的左边
- 或者把右子树最小值对应node移动到删除位置
- 。。。
- 所删除节点在左子树， 递归
- 所删除节点在右子树，递归
- 复杂度. 时间：O(h), h为树的高度。
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root == None:
return None
if root.val == key:
if root.right == None:
return root.left
root_new = root.right
cur = root.right
while cur.left:
cur = cur.left
cur.left = root.left
root = root_new
elif root.val > key:
root.left = self.deleteNode(root.left, key)
#if root.val < key:
else:
root.right = self.deleteNode(root.right, key)
return root
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
def traversal(root):
if root == None:
return None
if root.val > key:
root.left = traversal(root.left)
elif root.val < key:
root.right = traversal(root.right)
else:
if root.right == None:
return root.left
cur = root.right
while cur.left:
cur = cur.left
cur.left = root.left
root = root.right
return root
return traversal(root)
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root == None:
return root
if root.val > key:
root.left = self.deleteNode(root.left, key)
return root
elif root.val < key:
root.right = self.deleteNode(root.right, key)
return root
else:
righthead = root.right
if righthead == None:
return root.left
while righthead.left:
righthead = righthead.left
righthead.left = root.left
return root.right # !!!, not return righthead
- 迭代
- 需要人工维护parent信息
- 手动“删除”节点并完成新旧节点的链接
- 递归方法因为有额外的栈存储，不需要维护parent。并且链接可以简单递归更新root.left, root.right实现。
- 注意顺序，避免进入细节的讨论。比如：删除节点不在树中，删除节点在root，删除节点是叶子节点，。。。
- 找到欲删除节点后
- 第1步：把左子树merge到右子树，保存右子树的头结点subtree（注意右子树可能为空）
- 第2步：根据parent.val与Key的值，链接parent与subtree.
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root == None:
return None
dummyhead = TreeNode(float('inf'), root, None)
cur, parent = dummyhead, dummyhead
while cur:
if cur.val == key:
break
elif cur.val > key:
parent = cur
cur = cur.left
else:
parent = cur
cur = cur.right
# now cur is the node that needs to be deleted
if cur == None: # key is not on the tree
return dummyhead.left
#1 merge left-subtree and right-subtree, get the subroot for the new right-subtree
if cur.right:
subroot = cur.right #
node = cur.right
while node.left:
node = node.left
# link left-subtree to the left of the min of right-subtree
node.left = cur.left
else:
subroot = cur.left
#2 link parent and subtree
if parent.val > key: # parent.left = key
parent.left = subroot
else:
parent.right = subroot
return dummyhead.left
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root == None:
return None
if root.val == key:
if root.right == None:
return root.left
# 找出右子树的最小节点, 删除，然后重新"赋值"当前root
cur = root.right
while cur.left:
cur = cur.left
root.right = self.deleteNode(root.right, cur.val)
cur.left = root.left
cur.right = root.right
root = cur
elif root.val > key:
root.left = self.deleteNode(root.left, key)
else: # root.val < key
root.right = self.deleteNode(root.right, key)
return root
