时间戳

首页 > 技术文章 > 九章算法第三天，二叉树 分治

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

winters1992 2017-01-23 12:18 原文

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

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

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

最近公共祖先 III

 

其实这个问题  分治 travers 加上 hashMap 是最好解的办法，也最容易理解

 

/**
 * 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);
            }
        }
    }
}

 

这题完全是我自己想出来的暴力解法，一点都不优雅，因为题目自带的数据结构 没有提供compare接口，所以TreeSet无法使用，

 

幸好Java对象自带HashCode 所以用hashmap来存储状态树 是比较好的方式，不过这题 leetcode没法过，超时了 xxxx

lintcode还是可以过的，当然能写出来更低复杂度的更好，面试的时候 如果没有复杂度要求  怎么暴力 怎么好验证逻辑正确 就怎么来吧，

 

----------------------------------------

 

第二题   验证是否 二叉搜索树

Validate Binary Search Tree  

 

https://leetcode.com/problems/validate-binary-search-tree/

这个问题其实是我一个人调试差不多1小时 才出来的代码，期间演进了几遍 所以基本上算得是 带了很多混淆了

 

跟之前的思想是一致的，那就是举反例子，一旦出现不符合的递归定义的情形，  就锁住flag 然后不用继续往下递归 直接返回就好了

时间复杂度比较高 ，代码自带了逻辑混淆功能，  暂时还能看懂，3天之后 我估计我自己都看不懂了

 
class ParentDirection{
     public TreeNode node;
     public int turn;
     public ParentDirection(TreeNode node,int turn){
         this.node = node;
         this.turn = turn;
     }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    boolean isValidBST;
    boolean flag;
    
    public boolean isValidBST(TreeNode root) {
        // write your code here
        
        if (root == null){
            return true;
        }
        if(root.left == null && root.right==null){
            return true;
        }
        TreeNode rootParentNode = new TreeNode(-1);
        int turnflag = 0;//0 代表是第一次递归调用， -1 代表了一次 往左递归调用了一次  1代表往右递归调用了一次
        ParentDirection parentDirection = new ParentDirection(rootParentNode,0);//
        List<ParentDirection> list = new ArrayList<>();//加入了一个调用记录的List
        helper(root,list); 调用
        return isValidBST;
    }
    
    private void helper(TreeNode root,List<ParentDirection> list){
        
        if (root == null){
            return ;
        }
        
        for (ParentDirection p:list){//取出从根节点到当前节点的路径
            int turnflag = p.turn;  //取出递归的路径 是往右 还是 往左
            TreeNode rootParent = p.node;
            
            if ((root.right!=null&&turnflag==-1&&(root.right.val>=rootParent.val))||(root.left!=null&&turnflag==-1&&(root.left.val >= rootParent.val))){
                    isValidBST = false;
                    flag =true;
            }
        
            if ((root.left!=null&&turnflag==1&&(root.left.val <= rootParent.val))||(root.right!=null&&turnflag==1&&(root.right.val <= rootParent.val))){
                    isValidBST = false;
                    flag=true;
            }
        }
            
        if (flag==false && 
        (root.left == null || root.left.val < root.val  )&& 
        (root.right==null || root.right.val >root.val) ){
            isValidBST = true;
        }else{
            isValidBST = false;
            flag = true;
        }

        if (flag == true){//此树 已经不符合 二叉查找树定义 直接返回 无需继续递归下去
　　　　　　return;
　　　　 }

        List<ParentDirection> leftList = new ArrayList<ParentDirection>(list);
        leftList.add(new ParentDirection(root,-1));
        List<ParentDirection> rightList = new ArrayList<ParentDirection>(list);
        rightList.add(new ParentDirection(root,1));
        
        helper(root.left,leftList);//left sub Tree
        helper(root.right,rightList);//right sub Tree
    }
    
}

 

推荐阅读