LeetCode 236. [Java]Lowest Common Ancestor of a Binary Tree
原题链接
中等
作者:
tt2767
,
2022-04-20 16:46:09
,
所有人可见
,
阅读 271
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
1. 最近公共祖先, 是递归第一次即包含p也包含q的节点
2. 向下递归并返回状态
2.1包含p -> 返回1
2.2包含q -> 返回2
2.3 即包含p 也包含q || 都不包含 -> 返回0
其中第一次即包含p 也包含q 的子树根节点即为所求, 保存下来
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode[] result = new TreeNode[1];
isContainsNode(root, p, q, result);
return result[0];
}
public int isContainsNode(TreeNode root, TreeNode p, TreeNode q, TreeNode[] result) {
if (root == null) return 0;
boolean isP = root == p;
boolean isQ = root == q;
int left = isContainsNode(root.left, p, q, result);
int right = isContainsNode(root.right, p, q, result);
boolean foundLCA = isP && isQ
|| isP && (left == 2 || right == 2)
|| isQ && (left == 1 || right == 1)
|| left == 1 && right == 2
|| left == 2 && right == 1;
if (foundLCA && result[0] == null) result[0] = root;
if (isP || left == 1 || right == 1) return 1;
if (isQ || right == 2 || left == 2) return 2;
return 0;
}
}