[LeetCode]235. Lowest Common Ancestor of a Binary Search Tree

题目描述

思路

因为是二叉搜索树，因此如果两个节点的值都小于（或大于）当前节点，则需要移动当前节点到左（或右）子节点

代码

#include <iostream> using namespace std; 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) { if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q); if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q); return root; } }; int main() { TreeNode* node1 = new TreeNode(6); TreeNode* node2 = new TreeNode(2); TreeNode* node3 = new TreeNode(8); node1->left = node2; node1->right = node3; Solution s; cout << s.lowestCommonAncestor(node1, node2, node3)->val << endl; system("pause"); return 0; }