//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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
//
// Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
//
//
//
// Example 1:
//
//
//Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//Output: 3
//Explanation: The LCA of nodes 5 and 1 is 3.
//
//
// Example 2:
//
//
//Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//Output: 5
//Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
//
//
//
//
// Note:
//
//
// All of the nodes' values will be unique.
// p and q are different and both values will exist in the binary tree.
//
//

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */

package com.llz.algorithm.algorithm2019.secondweek;

import com.llz.algorithm.algorithm2019.firstweek.TreeNode;

import java.util.*;

public class LeetCode_236_2 {

    /**
     * Time complexity is O(n), space complexity is O(n).
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestorByIteration(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        Queue<TreeNode> queue = new ArrayDeque<>();
        Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
        map.put(root, null);
        queue.add(root);
        int find = 2;
        while (!queue.isEmpty() && find != 0) {
            root = queue.remove();
            if (root == p)
                find--;
            if (root == q)
                find--;
            if (root.left != null) {
                map.put(root.left, root);
                queue.add(root.left);
            }
            if (root.right != null) {
                map.put(root.right, root);
                queue.add(root.right);
            }
        }

        List<TreeNode> list = new ArrayList<>();
        TreeNode temp = q;
        while (q != null) {
            list.add(q);
            q = map.get(q);
        }

        while (!list.contains(p)) {
            p = map.get(p);
        }
        return p;
    }

    private TreeNode lca = null;

    /**
     * Time complexity is O(n), space complexity is O(n).
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        lca = null;
        dfs(root, p, q);
        return lca;
    }

    public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        int left = dfs(root.left, p, q) ? 1 : 0;
        int right = dfs(root.right, p, q) ? 1 : 0;
        int mid = 0;
        if (p == root | q == root) {
            mid = 1;
        }
        if (left + mid + right >= 2)
            lca = root;
        return (left + right + mid) > 0;
    }

    public static void test1() {
        TreeNode root = new TreeNode(3);
        TreeNode p = new TreeNode(5);
        root.left = p;
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        TreeNode q = new TreeNode(4);
        root.left.right.right = q;
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        LeetCode_236_2 lca = new LeetCode_236_2();
        TreeNode lc = lca.lowestCommonAncestor(root, p, q);
        System.out.println(lc.val);
    }

    public static void main(String[] args) {
        test1();
    }
}