/
githubmirror
/
interviews
Обзор
Документация
Войти
/
githubmirror
/
interviews
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
leetcode/tree/LowestCommonAncestorOfABinaryTree.java
38 строк
1 KB
Kevin Naughton Jr
finish renaming files and directories
27 мар 2018, 19:52
27 мар 2018, 19:52
ec6dfb5
Код
Авторство
О чём код?
// 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. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class LowestCommonAncestorOfABinaryTree { 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 ? right : left; } }