题目链接
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000
思路
- 从高度着手，父节点的高度肯定大于等于两个节点p、q的高度；
- 从高度相同的两个节点，一起往上走，相遇点即为父节点。
先找到p、q当前节点，高度较低的节点指针然后不断向上遍历，直到两个指针同一高度。同一高度之后，再同时向上遍历，直到相遇。
代码
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
class NewDot:def __init__(self,x):self.val = xself.h = 0self.left = Noneself.right = Noneself.pre = None
#建树，记录父节点，以及当前节点的高度
def build_new_tree(root:TreeNode, height):if root:new_dot = NewDot(root.val)new_dot.h = height + 1new_left = build_new_tree(root.left,height + 1)new_right = build_new_tree(root.right,height + 1)new_dot.left = new_leftnew_dot.right = new_rightif new_left:new_left.pre = new_dotif new_right:new_right.pre = new_dotreturn new_dotelse:return None
# 给一个值，递归找到当前节点
def search_node(root:NewDot,val):if root:return rootif root.val == val:return rootleft_node = search_node(root.left,val)if left_node:return left_nodeelse:return search_node(root.right,val)class Solution:def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:# 建新树new_dot = build_new_tree(root,0)# 找到两个节点位置low_node = search_node(new_dot,p)high_node = search_node(new_dot,q)# 往上遍历，使两者处于同一高度if low_node.h < high_node.h:low_node, high_node = high_node,low_nodediff_h = low_node.h - high_node.hwhile diff_h:low_node = low_node.prediff_h -= 1while low_node != high_node:low_node = low_node.prehigh_node = high_node.prereturn low_node.val看着大佬手撕之后，自己回去重新手撕一遍。这道题有两个基本功，一是，重新建一棵树，每个节点保存其父节点以及该节点的高度。二是，根据val值定位某个节点，使用递归，注意回传找到的节点。今天学习到了好多~ 开心~
)
