235. Lowest Common Ancestor of a Binary Search Tree（python+cpp）

题目：

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. 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).” Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note: All of the nodes’ values will be unique. p and q are different and both values will exist in the BST.

解释： 经典题目，最低公共祖先，用dfs做。 注意这里是BST，所以可以使用BST的特征，如果两个结点都比root小，那么在root的左子树寻找结果，如果两个结点的都比root大，那么在root的右子树上寻找，如果一个结点小于root（或者等于），另一个结点大于root（或者等于），这证明两个结点分别在root的左子树和右子树上，那么root就是他们最低的公共结点，返回root即可。 注意，一个结点可以是自己的祖先。 python代码：

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if p.val<root.val and q.val<root.val: return self.lowestCommonAncestor(root.left, p, q) elif p.val>root.val and q.val>root.val: return self.lowestCommonAncestor(root.right, p, q) else: return root

c++代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { int val=root->val; if(p->val<val&&q->val<val) return lowestCommonAncestor(root->left,p,q); else if (p->val>val &&q->val>val) return lowestCommonAncestor(root->right,p,q); return root; } };

总结： BST可以这么用，普通的二叉树就不行了哟～