美文网首页高薪算法+计算机职称考试算法算法编程
一篇文章搞定面试中的二叉树题目(java实现)

一篇文章搞定面试中的二叉树题目(java实现)

作者: IOExceptioner | 来源:发表于2016-11-18 22:05 被阅读17715次

    最近总结了一些数据结构和算法相关的题目,这是第一篇文章,关于二叉树的。
    先上二叉树的数据结构:

    class TreeNode{
        int val;
        //左孩子
        TreeNode left;
        //右孩子
        TreeNode right;
    }
    

    二叉树的题目普遍可以用递归和迭代的方式来解

    1.求二叉树的最大深度

    int maxDeath(TreeNode node){
        if(node==null){
            return 0;
        }
        int left = maxDeath(node.left);
        int right = maxDeath(node.right);
        return Math.max(left,right) + 1;
    }
    

    2.求二叉树的最小深度

        int getMinDepth(TreeNode root){
            if(root == null){
                return 0;
            }
            return getMin(root);
        }
        int getMin(TreeNode root){
            if(root == null){
                return Integer.MAX_VALUE;
            }
            if(root.left == null&&root.right == null){
                return 1;
            }
            return Math.min(getMin(root.left),getMin(root.right)) + 1;
        }
    

    3,求二叉树中节点的个数

        int numOfTreeNode(TreeNode root){
            if(root == null){
                return 0;
                
            }
            int left = numOfTreeNode(root.left);
            int right = numOfTreeNode(root.right);
            return left + right + 1;
        }
    

    4,求二叉树中叶子节点的个数

        int numsOfNoChildNode(TreeNode root){
            if(root == null){
                return 0;
            }
            if(root.left==null&&root.right==null){
                return 1;
            }
            return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
            
        }
    

    5.求二叉树中第k层节点的个数

            int numsOfkLevelTreeNode(TreeNode root,int k){
                if(root == null||k<1){
                    return 0;
                }
                if(k==1){
                    return 1;
                }
                int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
                int numsRight = numsOfkLevelTreeNode(root.right,k-1);
                return numsLeft + numsRight;
            }
    

    6.判断二叉树是否是平衡二叉树

        boolean isBalanced(TreeNode node){
            return maxDeath2(node)!=-1;
        }
        int maxDeath2(TreeNode node){
            if(node == null){
                return 0;
            }
            int left = maxDeath2(node.left);
            int right = maxDeath2(node.right);
            if(left==-1||right==-1||Math.abs(left-right)>1){
                return -1;
            }
            return Math.max(left, right) + 1;
        }
    

    7.判断二叉树是否是完全二叉树

    什么是完全二叉树呢?参见

        boolean isCompleteTreeNode(TreeNode root){
            if(root == null){
                return false;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            boolean result = true;
            boolean hasNoChild = false;
            while(!queue.isEmpty()){
                TreeNode current = queue.remove();
                if(hasNoChild){
                    if(current.left!=null||current.right!=null){
                        result = false;
                        break;
                    }
                }else{
                    if(current.left!=null&&current.right!=null){
                        queue.add(current.left);
                        queue.add(current.right);
                    }else if(current.left!=null&&current.right==null){
                        queue.add(current.left);
                        hasNoChild = true;
                        
                    }else if(current.left==null&&current.right!=null){
                        result = false;
                        break;
                    }else{
                        hasNoChild = true;
                    }
                }
                
            }
            return result;
        }
    

    8.两个二叉树是否完全相同

        boolean isSameTreeNode(TreeNode t1,TreeNode t2){
            if(t1==null&&t2==null){
                return true;
            }
            else if(t1==null||t2==null){
                return false;
            }
            if(t1.val != t2.val){
                return false;
            }
            boolean left = isSameTreeNode(t1.left,t2.left);
            boolean right = isSameTreeNode(t1.right,t2.right);
            return left&&right;
            
        }
    

    9.两个二叉树是否互为镜像

        boolean isMirror(TreeNode t1,TreeNode t2){
            if(t1==null&&t2==null){
                return true;
            }
            if(t1==null||t2==null){
                return false;
            }
            if(t1.val != t2.val){
                return false;
            }
            return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
            
        }
    

    10.翻转二叉树or镜像二叉树

        TreeNode mirrorTreeNode(TreeNode root){
            if(root == null){
                return null;
            }
            TreeNode left = mirrorTreeNode(root.left);
            TreeNode right = mirrorTreeNode(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
    

    11.求两个二叉树的最低公共祖先节点

        TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
            if(findNode(root.left,t1)){
                if(findNode(root.right,t2)){
                    return root;
                }else{
                    return getLastCommonParent(root.left,t1,t2);
                }
            }else{
                if(findNode(root.left,t2)){
                    return root;
                }else{
                    return getLastCommonParent(root.right,t1,t2)
                }
            }
        }
        // 查找节点node是否在当前 二叉树中
        boolean findNode(TreeNode root,TreeNode node){
            if(root == null || node == null){
                return false;
            }
            if(root == node){
                return true;
            }
            boolean found = findNode(root.left,node);
            if(!found){
                found = findNode(root.right,node);
            }
            return found;
        }
    

    12.二叉树的前序遍历

    迭代解法

        ArrayList<Integer> preOrder(TreeNode root){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(root == null){
                return list;
            }
            stack.push(root);
            while(!stack.empty()){
                TreeNode node = stack.pop();
                list.add(node.val);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left != null){
                    stack.push(node.left);
                }
                
            }
            return list;
        }
    

    递归解法

        ArrayList<Integer> preOrderReverse(TreeNode root){
            ArrayList<Integer> result = new ArrayList<Integer>();
            preOrder2(root,result);
            return result;
            
        }
        void preOrder2(TreeNode root,ArrayList<Integer> result){
            if(root == null){
                return;
            }
            result.add(root.val);
            preOrder2(root.left,result);
            preOrder2(root.right,result);
        }
    

    13.二叉树的中序遍历

        ArrayList<Integer> inOrder(TreeNode root){
            ArrayList<Integer> list = new ArrayList<<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode current = root;
            while(current != null|| !stack.empty()){
                while(current != null){
                    stack.add(current);
                    current = current.left;
                }
                current = stack.peek();
                stack.pop();
                list.add(current.val);
                current = current.right;
                
            }
            return list;
            
        }
    

    14.二叉树的后序遍历

        ArrayList<Integer> postOrder(TreeNode root){
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(root == null){
                return list;
            }
            list.addAll(postOrder(root.left));
            list.addAll(postOrder(root.right));
            list.add(root.val);
            return list;
        }
    

    15.前序遍历和后序遍历构造二叉树

        TreeNode buildTreeNode(int[] preorder,int[] inorder){
            if(preorder.length!=inorder.length){
                return null;
            }
            return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1);
        }
        TreeNode myBuildTree(int[] inorder,int instart,int inend,int[] preorder,int prestart,int preend){
            if(instart>inend){
                return null;
            }
            TreeNode root = new TreeNode(preorder[prestart]);
            int position = findPosition(inorder,instart,inend,preorder[start]);
            root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart);
            root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend);
            return root;
        }
        int findPosition(int[] arr,int start,int end,int key){
            int i;
            for(i = start;i<=end;i++){
                if(arr[i] == key){
                    return i;
                }
            }
            return -1;
        }
    

    16.在二叉树中插入节点

        TreeNode insertNode(TreeNode root,TreeNode node){
            if(root == node){
                return node;
            }
            TreeNode tmp = new TreeNode();
            tmp = root;
            TreeNode last = null;
            while(tmp!=null){
                last = tmp;
                if(tmp.val>node.val){
                    tmp = tmp.left;
                }else{
                    tmp = tmp.right;
                }
            }
            if(last!=null){
                if(last.val>node.val){
                    last.left = node;
                }else{
                    last.right = node;
                }
            }
            return root;
        }
    

    17.输入一个二叉树和一个整数,打印出二叉树中节点值的和等于输入整数所有的路径

        void findPath(TreeNode r,int i){
            if(root == null){
                return;
            }
            Stack<Integer> stack = new Stack<Integer>();
            int currentSum = 0;
            findPath(r, i, stack, currentSum);
            
        }
        void findPath(TreeNode r,int i,Stack<Integer> stack,int currentSum){
            currentSum+=r.val;
            stack.push(r.val);
            if(r.left==null&&r.right==null){
                if(currentSum==i){
                    for(int path:stack){
                        System.out.println(path);
                    }
                    
                }
            }
            if(r.left!=null){
                findPath(r.left, i, stack, currentSum);
            }
            if(r.right!=null){
                findPath(r.right, i, stack, currentSum);
            }
            stack.pop();
        }
    

    18.二叉树的搜索区间

    给定两个值 k1 和 k2(k1 < k2)和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。

        ArrayList<Integer> result;
        ArrayList<Integer> searchRange(TreeNode root,int k1,int k2){
            result = new ArrayList<Integer>();
            searchHelper(root,k1,k2);
            return result;
        }
        void searchHelper(TreeNode root,int k1,int k2){
            if(root == null){
                return;
            }
            if(root.val>k1){
                searchHelper(root.left,k1,k2);
            }
            if(root.val>=k1&&root.val<=k2){
                result.add(root.val);
            }
            if(root.val<k2){
                searchHelper(root.right,k1,k2);
            }
        }
    

    19.二叉树的层次遍历

        ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            if(root == null){
                return result;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                ArrayList<<Integer> level = new ArrayList<Integer>():
                for(int i = 0;i < size ;i++){
                    TreeNode node = queue.poll();
                    level.add(node.val);
                    if(node.left != null){
                        queue.offer(node.left);
                    }
                    if(node.right != null){
                        queue.offer(node.right);
                    }
                } 
                result.add(Level);
            }
            return result;
        }
    

    20.二叉树内两个节点的最长距离

    二叉树中两个节点的最长距离可能有三种情况:
    1.左子树的最大深度+右子树的最大深度为二叉树的最长距离
    2.左子树中的最长距离即为二叉树的最长距离
    3.右子树种的最长距离即为二叉树的最长距离
    因此,递归求解即可

    private static class Result{  
        int maxDistance;  
        int maxDepth;  
        public Result() {  
        }  
      
        public Result(int maxDistance, int maxDepth) {  
            this.maxDistance = maxDistance;  
            this.maxDepth = maxDepth;  
        }  
    }  
        int getMaxDistance(TreeNode root){
          return getMaxDistanceResult(root).maxDistance;
        }
        Result getMaxDistanceResult(TreeNode root){
            if(root == null){
                Result empty = new Result(0,-1);
                return empty;
            }
            Result lmd = getMaxDistanceResult(root.left);
            Result rmd = getMaxDistanceResult(root.right);
            Result result = new Result();
            result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1;
            result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance));
            return result;
        }
    

    21.不同的二叉树

    给出 n,问由 1...n 为节点组成的不同的二叉查找树有多少种?

        int numTrees(int n ){
            int[] counts = new int[n+2];
            counts[0] = 1;
            counts[1] = 1;
            for(int i = 2;i<=n;i++){
                for(int j = 0;j<i;j++){
                    counts[i] += counts[j] * counts[i-j-1];
                }
            }
            return counts[n];
        }
    

    22.判断二叉树是否是合法的二叉查找树(BST)

    一棵BST定义为:
    节点的左子树中的值要严格小于该节点的值。
    节点的右子树中的值要严格大于该节点的值。
    左右子树也必须是二叉查找树。
    一个节点的树也是二叉查找树。

        public int lastVal = Integer.MAX_VALUE;
        public boolean firstNode = true;
        public boolean isValidBST(TreeNode root) {
            // write your code here
            if(root==null){
                return true;
            }
            if(!isValidBST(root.left)){
                return false;
            }
            if(!firstNode&&lastVal >= root.val){
                return false;
            }
            firstNode = false;
            lastVal = root.val;
            if (!isValidBST(root.right)) {
                return false;
            }
            return true;
        }
    

    深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题。
    这里还有一篇关于二叉树的文章,一篇文章搞定面试中的链表题目

    相关文章

      网友评论

      • CodingLing:可不可以解释一下21的“不同二叉树”,不太明白算法的思路
      • huanfuan:有没有红黑树的
      • 6510103367a6:6.判断二叉树是否是平衡二叉树 这个好像不对,只判断了当前节点为根节点的树是否平衡,没有判断左右子树是否平衡
      • 84ff0624eee8:层次遍历是否冗余了?为什么每次只循环一个size的长度,直接循环到底不就得了
      • 贾智文:两个节点最远距离的算法应该是有问题的。 少了2.
      • 6cc01719e0fe:不错不错,收藏了。

        推荐下,源码圈 300 胖友的书单整理:http://t.cn/R0Uflld


        12a033ef755a:写的不错,谢谢博主;已收藏~
      • stefan_zhou:构造二叉树是先序和后序,应该是先序中序吧? 另外该函数的findposition调用里面的start参数错了吧???
      • faf35009f9b4:楼主迭代中的前序方法有误,if条件中的内容和执行体不应该是root.left和root.right,而是node.left和node.right。
        faf35009f9b4:@IOExceptioner 共勉共勉:smile:
        IOExceptioner:@Kevin先生 感谢更正,我下班会更改。
      • 枫叶红花:能不能讲下二叉树的原理,和实现方法。。我记得还有另一种
      • MiBoy:请问 最常问的都是哪几个呢
      • AllenCoder:我最近也在准备跳槽的面试
      • 小小小__:希望写一下非递归实现的代码

      本文标题:一篇文章搞定面试中的二叉树题目(java实现)

      本文链接:https://www.haomeiwen.com/subject/glfjpttx.html