LintCode 578 Lowest Common Ancestor III

思路

基本与LCA那题类似，判断树根和子树，只是需要额外保存A，B节点是否在node的子树中存在的信息。使用ResultType来保存该信息。

复杂度

时间复杂度O(n)
空间复杂度O(n)

代码

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/class ResultType {
    boolean a_exist, b_exist;TreeNode node;public ResultType(boolean a_exist, boolean b_exist, TreeNode node) {
    this.a_exist = a_exist;this.b_exist = b_exist;this.node = node;}
}public class Solution {
    /** @param root: The root of the binary tree.* @param A: A TreeNode* @param B: A TreeNode* @return: Return the LCA of the two nodes.*/public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
    // write your code hereResultType result = helper(root, A, B);if (result.a_exist && result.b_exist) {
    return result.node;}return null;}private ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
    if (root == null) {
    return new ResultType(false, false, null);}ResultType left = helper(root.left, A, B);ResultType right = helper(root.right, A, B);boolean a_exist = left.a_exist || right.a_exist || A == root;boolean b_exist = left.b_exist || right.b_exist || B == root;if (A == root || B == root) {
    return new ResultType(a_exist, b_exist, root);}if (left.node != null && right.node != null) {
    return new ResultType(a_exist, b_exist, root);}if (left.node != null) {
    return new ResultType(a_exist, b_exist, left.node);}if (right.node != null) {
    return new ResultType(a_exist, b_exist, right.node);}return new ResultType(a_exist, b_exist, null);}
}