代码随想录算法训练营第二十二天|235. 二叉搜索树的最近公共祖先,701. 二叉搜索树中的插入操作

[参考链接]

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