Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the?definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes?p?and?q?as the lowest node in?T?that has both?p?and?q?as descendants (where we allow?a node to be a descendant of itself).”
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
题目中给了限制条件，每个node都是独一无二的且p！=q。
思路：
自下到上对树进行查找，后序遍历就是这样天然的回溯过程。
如何判断一个节点是否是p和q的公共祖先呢？如果找到一个节点，发现p在其左子树，q在其右子树或者反之，该节点即是公共祖先。注意，有可能某节点并没有左或者右子树了，即该节点自己既是p或者q，又是待求的公共祖先。
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root == q or root == p or root is None:
return root
# return value
left = self.lowestCommonAncestor(root.left, p, q) # left
right = self.lowestCommonAncestor(root.right, p, q) # right
if left is not None and right is not None: # middle
return root
if left is None and right is not None:
return right
elif left is not None and right is None:
return left
else:
return None You are given the?root?node of a binary search tree (BST) and a?value?to insert into the tree. Return?the root node of the BST after the insertion. It is?guaranteed?that the new value does not exist in the original BST.
Notice?that there may exist?multiple valid ways for the?insertion, as long as the tree remains a BST after insertion. You can return?any of them.
思路：这道题仅仅是要求以合理方式把一个值插入二叉树搜索树中，由于二叉搜索树是有排序的（右子树值>父节点值>左子树值），所以只要把这个值插入到叶节点下就是合理的，这样原有的tree的结构几乎不用调整。那关键就在于如何找到这个叶节点。这里用preorder前序遍历。
递归函数 traversal:
cur 和要插入的值 val 作为参数。cur is None），意味着已经到达了应该插入新节点的位置。这里创建一个新节点，并根据值的大小决定是连接到父节点的左侧还是右侧。val 和当前节点值 cur.val 的比较结果决定是向左子树递归还是向右子树递归。这是前序遍历的特征，因为操作是在递归调用前进行的。前序遍历（Preorder Traversal）:
函数 insertIntoBST:
traversal 函数来找到正确的插入位置。class Solution(object):
def __init__(self):
self.parent = None
def traversal(self, cur, val):
if cur is None:
node = TreeNode(val)
if val > self.parent.val:
self.parent.right = node
else:
self.parent.left = node
return
self.parent = cur
if cur.val > val: # This is a binary search tree!! (nodes are sorted).
self.traversal(cur.left, val)
#if cur.val < val:
else:
self.traversal(cur.right, val)
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if root is None:
root = TreeNode(val)
else:
self.traversal(root,val)
return root
以及迭代法：这题似乎迭代法更容易理解一些？?
class Solution:
def insertIntoBST(self, root, val):
if root is None: # 如果根节点为空，创建新节点作为根节点并返回
node = TreeNode(val)
return node
cur = root
parent = root # 记录上一个节点，用于连接新节点
while cur is not None:
parent = cur
if cur.val > val:
cur = cur.left
else:
cur = cur.right
node = TreeNode(val)
if val < parent.val:
parent.left = node # 将新节点连接到父节点的左子树
else:
parent.right = node # 将新节点连接到父节点的右子树
return root
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return?the?root node reference?(possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
思路：删除binary search tree的一个节点比加入一个节点要难。因为如果被删除的节点左右子树都存在，那么就需要考虑补位问题。这里讨论四种删除节点的可能性：（见以下解答的comments）
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if root is None:
return root
if root.val == key:
if root.left is None and root.right is None: # case1: 待删除的节点是叶节点，直接删除
return None
elif root.left is None: # case2: 无左子树，那直接右子树补位
return root.right
elif root.right is None: # case3: 无右子树，那直接左子树补位
return root.left
else: # case4: 左右子树都存在，将左子树放到删除的节点的柚子树的最左边节点的左叶子上。返回右子树.
cur = root.right
while cur.left is not None:
cur = cur.left
cur.left = root.left
return root.right
if root.val > key:
root.left = self.deleteNode(root.left, key)
if root.val < key:
root.right = self.deleteNode(root.right, key)
return root 递归法二：
class Solution:
def deleteNode(self, root, key):
if root is None: # 如果根节点为空，直接返回
return root
if root.val == key: # 找到要删除的节点
if root.right is None: # 如果右子树为空，直接返回左子树作为新的根节点
return root.left
cur = root.right
while cur.left: # 找到右子树中的最左节点
cur = cur.left
root.val, cur.val = cur.val, root.val # 将要删除的节点值与最左节点值交换
root.left = self.deleteNode(root.left, key) # 在左子树中递归删除目标节点
root.right = self.deleteNode(root.right, key) # 在右子树中递归删除目标节点
return root迭代法：总感觉迭代法相对递归法更容易理解，尤其是对于BST。
class Solution:
def deleteOneNode(self, target: TreeNode) -> TreeNode:
"""
将目标节点（删除节点）的左子树放到目标节点的右子树的最左面节点的左孩子位置上
并返回目标节点右孩子为新的根节点
是动画里模拟的过程
"""
if target is None:
return target
if target.right is None:
return target.left
cur = target.right
while cur.left:
cur = cur.left
cur.left = target.left
return target.right
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if root is None:
return root
cur = root
pre = None # 记录cur的父节点，用来删除cur
while cur:
if cur.val == key:
break
pre = cur
if cur.val > key:
cur = cur.left
else:
cur = cur.right
if pre is None: # 如果搜索树只有头结点
return self.deleteOneNode(cur)
# pre 要知道是删左孩子还是右孩子
if pre.left and pre.left.val == key:
pre.left = self.deleteOneNode(cur)
if pre.right and pre.right.val == key:
pre.right = self.deleteOneNode(cur)
return root