二叉树搜索树的最近公共祖先
递归法(非回溯)
搜索二叉树不需要回溯,直接判断当前点在目标点两端就可以。普通二叉树要回溯
/** * 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* find_node(TreeNode* cur, TreeNode* p, TreeNode* q) { //发现目标点或者空点返回 if(cur==NULL || cur->val == p->val || cur->val == q->val) return cur; //当前值大于目标点,则目标点在左子树 if(cur->val > p->val && cur->val > q->val) { TreeNode * left_tree = find_node(cur->left,p,q); return left_tree; } //当前值小于目标点,则目标点在右子树 else if (cur->val < p->val && cur->val < q->val) { TreeNode * right_tree = find_node(cur->right,p,q); return right_tree; } //当前值在两个目标点中间,则当前值是公共祖先返回 else { return cur; } } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return find_node(root,p,q); } };
二刷
/** * 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* result; int track_back(TreeNode* cur, TreeNode* p, TreeNode* q) { if(cur == NULL) return 0; int flag = 0; TreeNode *left_node; TreeNode *right_node; if(p->val <= q->val) { left_node = p; right_node = q; }else { left_node = q; right_node = p; } if(cur->val >= left_node->val && cur->val <= right_node->val ) { flag += track_back(cur->left,p,q); flag += track_back(cur->right,p,q); }else if(cur->val < left_node->val) flag += track_back(cur->right,p,q); else if(cur->val > right_node->val) flag += track_back(cur->left,p,q); if(cur == left_node) flag += 1; else if(cur == right_node) flag +=2; if(flag == 3 ) { result = cur; return 0; } return flag; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { track_back(root,p,q); return result; } };