代码拉取完成,页面将自动刷新
package com.fishercoder.solutions;
import com.fishercoder.common.classes.TreeNode;
/**
* 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.*/
public class _236 {
public static class Solution1 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。