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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
- _______6______
- / ___2__ ___8__
- / \ / 0 _4 7 9
- / 3 5
For example, the lowest common ancestor (LCA) of nodes
and
- 2
is
- 8
. Another example is LCA of nodes
- 6
and
- 2
is
- 4
, since a node can be a descendant of itself according to the LCA definition.
- 2
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * public int val;
- * public TreeNode left;
- * public TreeNode right;
- * public TreeNode(int x) { val = x; }
- * }
- */
- public class Solution {
- public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if (root == null) return null;
- if (p.val < root.val && q.val < root.val)
- {
- return LowestCommonAncestor(root.left, p, q);
- }
- else if (p.val > root.val && q.val > root.val)
- {
- return LowestCommonAncestor(root.right, p, q);
- }
- return root;
- }
- }
- // it work for any binary tree including BST
- public class Solution1 {
- private bool LCA(TreeNode root, TreeNode p, TreeNode q, bool[] found)
- {
- if (root == p)
- {
- found[0] = true;
- }
- if (root == q)
- {
- found[1] = true;
- }
- if (found[0] && found[1]) return true;
- if (root == null) return false;
- return LCA(root.left, p, q, found) || LCA(root.right, p, q, found);
- }
- public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if (root == null) return null;
- if (LCA(root.left, p, q, new bool[2]))
- {
- return LowestCommonAncestor(root.left, p, q);
- }
- else if (LCA(root.right, p, q, new bool[2]))
- {
- return LowestCommonAncestor(root.right, p, q);
- }
- return root;
- }
- }
来源: http://www.bubuko.com/infodetail-2415544.html