九章算法第三天，二叉树 分治

给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。

两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。

返回 null 如果两个节点在这棵树上不存在最近公共祖先的话。

/**
 * 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;
 *     }
 * }
 */
public class Solution {
     /**
     * @param root The root of the binary tree.
     * @param A and B two nodes
     * @return: Return the LCA of the two nodes.
     */

    TreeNode tmpParent;

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if(root==null){
            return null;
        }
        Map<TreeNode,Integer> map = new HashMap<TreeNode,Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode tmpNode;
        while(!stack.empty()){
            tmpNode = stack.pop();
            map.put(tmpNode,1);
            if (tmpNode.left!=null){
                stack.push(tmpNode.left);
            }
            if (tmpNode.right!=null){
                stack.push(tmpNode.right);
            }
        }//先中序遍历整个二叉树
　　　　　　
        if (map.containsKey(A)==false || map.containsKey(B)==false){
            return null;//找不到 直接null
        }
        //tmpParent = root;
        helper(map,root,A,B);
        return tmpParent;
    }

    public void helper(Map<TreeNode,Integer> map,TreeNode root, TreeNode A, TreeNode B){
        if (root == null){
            return;
        }

        if (map.containsKey(A)&&map.containsKey(B)){//每次递归 就会找到离 最近公共祖先  更近的节点 最后tempParent就是最近祖先
            tmpParent = root;
        }else{
　　　　 　　 return;//要么找到了A 要么找到了B 要么都没有 这种情况，就没没必要再继续递归下去了
　　　　　} 
　　　　 //如果当前节点下包含 两个节点 那么就是临时 Parent就是root
        map.remove(root);//删除目前的根节点

        Map<TreeNode,Integer> leftMap = new HashMap<TreeNode,Integer>(map);//拷贝下map
        Map<TreeNode,Integer> rightMap = new HashMap<TreeNode,Integer>(map);//拷贝下map

        remover(leftMap,root.right);//暴力删除友子树
        remover(rightMap,root.left);//暴力删除左子树

        helper(leftMap,root.left,A,B);//分治递归左边
        helper(rightMap,root.right,A,B);//分治递归右边 
    }

    private void remover(Map<TreeNode,Integer> maps,TreeNode node){
        if (node == null){
            return;
        }
        TreeNode tmpNode;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(node);
        while(!stack.empty()){
            tmpNode = stack.pop();
            maps.remove(tmpNode);
            if (tmpNode.left!=null){
                stack.push(tmpNode.left);
            }
            if (tmpNode.right!=null){
                stack.push(tmpNode.right);
            }
        }
    }
}