这是个BST，是有顺序的.......有顺序就好办了.......
/** * 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) { if(root==NULL||p==NULL||q==NULL) return NULL; /* while((root->val-p->val)*(root->val-q->val)>0) { root=(root->val)>(p->val)?(root->left):(root->right); } return root; */ if(root->val>p->val&&root->val>q->val) { return lowestCommonAncestor(root->left, p, q); } if(root->val<p->val&&root->val<q->val) { return lowestCommonAncestor(root->right, p, q); } return root; } };之前忽略了有顺序的N^2复杂度的 /** * 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) { if(root==NULL) return root; if(findTreeNode(root->left,p)&&findTreeNode(root->left,q)) return lowestCommonAncestor(root->left,p,q); if(findTreeNode(root->right,p)&&findTreeNode(root->right,q)) return lowestCommonAncestor(root->right,p,q); return root; } bool findTreeNode(TreeNode * root,TreeNode * p) { if(root==NULL) return false; if(root==p) return true; if(findTreeNode(root->left,p)||findTreeNode(root->right,p)) return true; else return false; } };