# 【刷题】Lowest Common Ancestor

2018-03-01 11:18:01来源:https://www.jianshu.com/p/ea115f225abc作者:猴子007人点击

basic problem

leetcode戳我

Description

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Notice:

Assume two nodes are exist in tree.

Example

For the following binary tree:

``  4 / /3   7   / /  5   6``

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
Tags

`LinkedIn` `LintCode Copyright` `Binary Tree` `Facebook`

``class TreeNode {  int val;  TreeNode left;  TreeNode right;  TreeNode(int x) {    val = x;  }}// 两节点在树中public class Solution {  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    if (root == null) {      return null;    }    // p and q must exist in tree, so that lca of p and q must exist    return findMostPossibleLCA(root, p, q);  }  private TreeNode findMostPossibleLCA(TreeNode root, TreeNode node1, TreeNode node2) {    if (root == null) {      return null;    }    if (root == node1 || root == node2) {      return root;    }    TreeNode leftPLCA = findMostPossibleLCA(root.left, node1, node2);    TreeNode rightPLCA = lowestCommonAncestor(root.right, node1, node2);    if (leftPLCA == null && rightPLCA == null) {      // must not exist LCA      return null;    }    if (leftPLCA != null && rightPLCA != null) {      // must be LCA      return root;    }    // most possible be LCA    return leftPLCA != null ? leftPLCA : rightPLCA;  }}``

lintcode戳我

Description

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attribute `parent` which point to the father of itself. The root's parent is null.

Notice:

Assume two nodes are exist in tree.

Example

For the following binary tree:

``  4 / /3   7   / /  5   6``

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
Tags

`LintCode Copyright` `Binary Tree`

``class ParentTreeNode {  public ParentTreeNode parent, left, right;}public class FollowUp1 {  // 1. 先分别向上遍历到root，得到两个深度d1，d2  // 2. 回到节点位置，更深的先向上走abs(d1-d2)步  // 3. 然后二者一起走min(d1,d2)步，过程中一定会有根节点  // 时间O(lgn)，空间O(1)  public ParentTreeNode lowestCommonAncestor(ParentTreeNode root,                                             ParentTreeNode p,                                             ParentTreeNode q) {    ParentTreeNode node1 = p;    ParentTreeNode node2 = q;    if (root == null || node1 == null || node2 == null) {      return null;    }    int depth1 = getDepth(root, node1);    int depth2 = getDepth(root, node2);    if (depth1 == -1 || depth2 == -1) {      return null;    }    ParentTreeNode startNode1 = node1;    ParentTreeNode startNode2 = node2;    int depth = depth1;    if (depth1 > depth2) {      for (int i = 0; i < depth1 - depth2; i++) {        startNode1 = startNode1.parent;      }      depth = depth2;    } else if (depth1 < depth2) {      for (int i = 0; i < depth2 - depth1; i++) {        startNode2 = startNode2.parent;      }      depth = depth1;    }    for (int i = 0; i < depth; i++) {      if (startNode1 == startNode2) {        return startNode1;      }      startNode1 = startNode1.parent;      startNode2 = startNode2.parent;    }    throw new RuntimeException("UnknownError");  }  private int getDepth(ParentTreeNode root, ParentTreeNode target) {    int depth = 1;    ParentTreeNode node = target;    for (; node.parent != null; node = node.parent) {      if (node == root) {        break;      }      depth++;    }    if (node == root) {      return depth;    }    return -1;  }}``

lintcode戳我

Description

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Return null if LCA does not exist.

Notice:

node A or node B may not exist in tree.

Example

For the following binary tree:

``  4 / /3   7   / /  5   6``

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
Tags

`LinkedIn` `LintCode Copyright` `Binary Tree` `Facebook`

``public class FollowUp2 {  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    TreeNode node1 = p;    TreeNode node2 = q;    if (root == null || node1 == null || node2 == null) {      return null;    }    Stack<TreeNode> path1 = new Stack<>();    if (!dfsPreorder(root, node1, path1)) {      return null;    }    Stack<TreeNode> path2 = new Stack<>();    if (!dfsPreorder(root, node2, path2)) {      return null;    }    TreeNode lca = null;    for (int i = 0; i < path1.size() && i < path2.size(); i++) {      if (path1.get(i) != path2.get(i)) {        break;      }      lca = path1.get(i);    }    return lca;  }  private boolean dfsPreorder(TreeNode root, TreeNode node, Stack<TreeNode> path) {    path.push(root);    if (root == node) {      return true;    }    if (root.left != null && dfsPreorder(root.left, node, path)) {      return true;    }    if (root.right != null && dfsPreorder(root.right, node, path)) {      return true;    }    path.pop();    return false;  }}``