235. 二叉搜索树的最近公共祖先
[注意]
1.因为是有序树，所以如果中间节点是 q 和 p 的公共祖先，那么中间节点的数组 一定是在[p, q]区间的。即中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。
2.那么只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是q 和 p的公共祖先。
3.遍历顺序无所谓,没有中间处理逻辑,只要有一个左一个右就可以.
[代码]
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution(object): 9 def lowestCommonAncestor(self, root, p, q): 10 """ 11 :type root: TreeNode 12 :type p: TreeNode 13 :type q: TreeNode 14 :rtype: TreeNode 15 """ 16 #1.递归法 17 #左 18 if root.val > p.val and root.val > q.val: 19 return self.lowestCommonAncestor(root.left, p, q) 20 #右 21 if root.val < p.val and root.val < q.val: 22 return self.lowestCommonAncestor(root.right, p, q) 23 #cur处在中间 24 return root 25 26 #2.迭代法 27 while True: 28 if root.val > p.val and root.val > q.val: 29 root = root.left 30 elif root.val < p.val and root.val < q.val: 31 root = root.right 32 else: 33 return root
701. 二叉搜索树中的插入操作
[注意]
1.只要遍历二叉搜索树，找到空节点 插入元素就可以了，
2.把添加的节点返回给上一层，就完成了父子节点的赋值操作了，
[代码]
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, val=0, left=None, right=None): 4 # self.val = val 5 # self.left = left 6 # self.right = right 7 class Solution(object): 8 def insertIntoBST(self, root, val): 9 """ 10 :type root: TreeNode 11 :type val: int 12 :rtype: TreeNode 13 """ 14 # 返回更新后的以当前root为根节点的新树，方便用于更新上一层的父子节点关系链 15 16 # Base Case 17 if not root: return TreeNode(val) 18 19 # 单层递归逻辑: 20 if val < root.val: 21 # 将val插入至当前root的左子树中合适的位置 22 # 并更新当前root的左子树为包含目标val的新左子树 23 root.left = self.insertIntoBST(root.left, val) 24 25 if root.val < val: 26 # 将val插入至当前root的右子树中合适的位置 27 # 并更新当前root的右子树为包含目标val的新右子树 28 root.right = self.insertIntoBST(root.right, val) 29 30 # 返回更新后的以当前root为根节点的新树 31 return root