赞
踩
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).”
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.
- /**
- * 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 NULL;
- if(root->val < min(p->val,q->val)) return lowestCommonAncestor(root->right, p, q);
- else if (root->val > max(p->val,q->val)) return lowestCommonAncestor(root->left, p, q);
- else return root;
- }
- };
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if (root == null) {return null;}
- if (root.val < Math.min(p.val, q.val)) {return lowestCommonAncestor(root.right, p, q);}
- else if (root.val > Math.max(p.val, q.val)) {return lowestCommonAncestor(root.left, p, q);}
- else {return root;}
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。