LeetCode:235. 二叉搜索树的最近公共祖先

/** * 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) { /* 算法 从根节点开始遍历树 如果节点 p 和节点 q 都在右子树上，那么以右孩子为根节点继续 1 的操作 如果节点 p 和节点 q 都在左子树上，那么以左孩子为根节点继续 1 的操作 如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了 */ if(root==NULL) { return NULL; } if(p->val>root->val&&q->val>root->val) { return lowestCommonAncestor(root->right,p,q); } else if(p->val<root->val&&q->val<root->val) { return lowestCommonAncestor(root->left,p,q); } else{ return root; } } };