首页 > 代码库 > 236. Lowest Common Ancestor of a Binary Tree
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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).”
_______3______
/ ___5__ ___1__
/ \ / 6 _2 0 8
/ 7 4
For example, the lowest common ancestor (LCA) of nodes
5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.二刷 ４０％
思考：遍历到节点ｎｏｄｅ，要判断它是否是ｐ、q的ＬＣＡ，想知道ｎｏｄｅ是否等于p、q，以及ｎｏｄｅ的左子树和右子树里包含p,q的情况。
建一个helper function，返回以ｎｏｄｅ为根的树里包含p、q的情况。
若返回１，表示包含p; 若返回２，表示包含ｑ; 若返回３，表示包含p和ｑ; 若返回０，表示都不包含。
遍历到ｎｏｄｅ，可以分这几种情况：
如果 node == p,再看ｎｏｄｅ的左右子树里是否包含q，如果包含返回３，并且把ｎｏｄｅ设为ｒｅｓｕｌｔ
如果 node == q,再看ｎｏｄｅ的左右子树里是否包含p，如果包含返回３，并把ｎｏｄｅ设为ｒｅｓｕｌｔ
如果 node != p 且node != q
看ｎｏｄｅ的左子树，如果返回３(包含p、q)，则返回３（但不需要设置result, 因为ｒｅｓｕｌｔ应该在ｒｏｏｔ的左子树里）
同理看ｎｏｄｅ的右子树，如果返回３，则ｒｏｏｔ也返回３
如果helper(root.left) + helper(root.right) == 3，说明p和q一个在ｒｏｏｔ的左子树里，一个在右子树里，把ｒｏｏｔ设为ｒｅｓｕｌｔ，返回３
所有为３的情况都返回了，不为３的话返回helper(root.left) + helper(root.right)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode node = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
findNode(root, p, q);
return node;
}
public int findNode(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return 0;
}
int re = 0;
if (root == p) {
re = 1 + findNode(root.left, p, q) + findNode(root.right, p, q);
} else if (root == q) {
re = 2 + findNode(root.left, p, q) + findNode(root.right, p, q);
} else {
int left = findNode(root.left, p, q);
if (left == 3) {
return 3;
}
int right = findNode(root.right, p, q);
if (right == 3) {
return 3;
}
re = left + right;
}
if (re == 3) {
node = root;
}
return re;
}
}
recursively root,检查root是否是pq，root的左子树是否有pq，root的右子树是否有pq。 18%
如果左子树不含pq，lowestCommonAncestor(root.right,p,q)返回空，LCA在右子树中。
递归，检查root，检查root.left, 检查root.right
**这种办法是基于p、q一定在ｒｏｏｔ中
/**
* Definition for a binary tree node.
* public 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;
if(root==p || root==q) return root;
TreeNode left=lowestCommonAncestor(root.left, p, q), right = lowestCommonAncestor(root.right, p, q);
if(left!=null && right!=null) return root;
if(right==null) return left;
if(left==null) return right;
return null;
}
}
236. Lowest Common Ancestor of a Binary Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。