文档章节

剑指Offer(Java版):二叉树的深度

一贱书生
 一贱书生
发布于 2016/08/03 09:40
字数 1638
阅读 4
收藏 0

题目:输入一棵二叉树的根节点,求该数的深度。从根节点到叶结点依次进过的结点(含根,叶结点)形成树的一条路径,最长路径的长度为树的深度。

例如,如下图的二叉树的深度为4,因为它从根节点到叶结点的最长的路径包含4个结点(从根结点1开始,经过2和结点5,最终到达叶结点7)

我们可以从另一种角度来理解树的深度。如果一棵树只有一个结点,它的 深度为1,如果根节点只有左子树而没有右子树,那么树的深度应该是其左子树的深度+1.同样如果根节点只有右子树而没有左子树,那么树的深度应该是其右子 树+1.如果既有左子树又有右子树,那概述的深度就是左、右子树的深度的较大值加1.。

利用这个思路,我们可以用递归来实现代码:

package cglib;

class BinaryTreeNode{
    int data;
    
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
    
}

public class jiekou {

    //普通二叉树求深度  
    public int treeDepth(BinaryTreeNode root){  
        if(root == null)  
            return 0;  
        System.out.println("treeDepth递归");
        int nLeft = treeDepth(root.leftNode);
        
        System.out.println("nLeft="+nLeft);
        System.out.println("nRight前treeDepth递归");
        int nRight = treeDepth(root.rightNode);
        System.out.println("nRight后");
        System.out.println("nRight="+nRight);
        return (nLeft > nRight)?(nLeft+1):(nRight+1);  
    }   
        public static void main(String[] args){  
            BinaryTreeNode root=new BinaryTreeNode();
            BinaryTreeNode node1=new BinaryTreeNode();
            BinaryTreeNode node2=new BinaryTreeNode();
            BinaryTreeNode node3=new BinaryTreeNode();
            BinaryTreeNode node4=new BinaryTreeNode();
            BinaryTreeNode node5=new BinaryTreeNode();
            BinaryTreeNode node6=new BinaryTreeNode();
            root.leftNode=node1;
            root.rightNode=node2;
            node1.leftNode=node3;
            node1.rightNode=node4;
            node2.rightNode=node5;
            node4.leftNode=node6;
            root.data=1;
            node1.data=2;
            node2.data=3;
            node3.data=4;
            node4.data=5;
            node5.data=6;
            node6.data=7;
            jiekou test = new jiekou();  
            System.out.println(test.treeDepth(root));  
        }
    }

输出:4

 

 

如果公司对编程能力有较高的要求,面试官可能会追加一个与前面的问题相关但难度较大的问题,比如,应聘者做完上面的问题后,面试官追问:

 

题目二:输入一棵二叉树的根节点,判断该树是不是平衡的二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

需要重复遍历结点多次的解法,简单但不足以打动面试官

有了求二叉树的深度的经验之后再解决这个问题,我们很容易就能想到一个思路:在遍历树的每个结点的时候,调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差不超过1,按照定义它就是一棵平衡的二叉树。这种思路实现的代码如下:

 

package cglib;

class BinaryTreeNode{
    int data;
    
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
    
}

public class jiekou {

    //普通二叉树求深度  
    public int treeDepth(BinaryTreeNode root){  
        if(root == null)  
            return 0;  
        System.out.println("treeDepth递归");
        int nLeft = treeDepth(root.leftNode);
        
        System.out.println("nLeft="+nLeft);
        System.out.println("nRight前treeDepth递归");
        int nRight = treeDepth(root.rightNode);
        System.out.println("nRight后");
        System.out.println("nRight="+nRight);
        return (nLeft > nRight)?(nLeft+1):(nRight+1);  
    }
    
    public boolean isBalanced(BinaryTreeNode root){  
        if(root ==null)  
            return true;  
        int left = treeDepth(root.leftNode);  
        int right = treeDepth(root.rightNode);  
        int diff = left - right;  
        if(diff > 1 || diff <-1)  
            return false;  
        return isBalanced(root.leftNode) && isBalanced(root.rightNode);  
    }  
        public static void main(String[] args){  
            BinaryTreeNode root=new BinaryTreeNode();
            BinaryTreeNode node1=new BinaryTreeNode();
            BinaryTreeNode node2=new BinaryTreeNode();
            BinaryTreeNode node3=new BinaryTreeNode();
            BinaryTreeNode node4=new BinaryTreeNode();
            BinaryTreeNode node5=new BinaryTreeNode();
            BinaryTreeNode node6=new BinaryTreeNode();
            root.leftNode=node1;
            root.rightNode=node2;
            node1.leftNode=node3;
            node1.rightNode=node4;
            node2.rightNode=node5;
            node4.leftNode=node6;
            root.data=1;
            node1.data=2;
            node2.data=3;
            node3.data=4;
            node4.data=5;
            node5.data=6;
            node6.data=7;
            jiekou test = new jiekou();  
            System.out.println(test.treeDepth(root));
            System.out.println(test.isBalanced(root));
        }
    }

 

输出:

treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=2
nLeft=3
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=1
nRight后
nRight=2
4
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=2
treeDepth递归
nLeft=0
nRight前treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nRight后
nRight=1
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
nLeft=1
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
treeDepth递归
nLeft=0
nRight前treeDepth递归
nRight后
nRight=0
true

上面的代码固然简洁,但我们也注意到由于一个结点会被重复遍历多次,这种 思路的时间效率不高。例如在函数isBalanced中输入上图中的二叉树,我们将首先判断根节点是不是平衡的。此时我们网函数TreeDepth输入左 子树的根节点时需要遍历结点4,5,7.接下来判断以结点2为根节点的子树是不是平衡树的时候,仍然会遍历结点4,5,7.毫无疑问,重复遍历同一个结点 会影响性能。接下来我们寻找不需要重复遍历的算法。

package cglib;

class BinaryTreeNode{
    int data;
    
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
    
}

public class jiekou {

    //普通二叉树求深度  
    public int treeDepth(BinaryTreeNode root){  
        if(root == null)  
            return 0;  
        System.out.println("treeDepth递归");
        int nLeft = treeDepth(root.leftNode);
        
        System.out.println("nLeft="+nLeft);
        System.out.println("nRight前treeDepth递归");
        int nRight = treeDepth(root.rightNode);
        System.out.println("nRight后");
        System.out.println("nRight="+nRight);
        return (nLeft > nRight)?(nLeft+1):(nRight+1);  
    }
    
    public boolean isBalanced(BinaryTreeNode root){  
        if(root ==null)  
            return true;  
        int left = treeDepth(root.leftNode);  
        int right = treeDepth(root.rightNode);  
        int diff = left - right;  
        if(diff > 1 || diff <-1)  
            return false;  
        return isBalanced(root.leftNode) && isBalanced(root.rightNode);  
    }  
    
    //高效率的判断是否是一棵平衡二叉树  
    public boolean isBalanced2(BinaryTreeNode root){  
        int depth = 0;  
        return isBalanced2(root,depth);  
    }  
    public boolean isBalanced2(BinaryTreeNode root,int depth){  
        if(root == null){  
            depth = 0;  
            return true;  
        }  
        int left = 0,right = 0;  
        if(isBalanced2(root.leftNode,left) && isBalanced2(root.rightNode,right)){  
            int diff = left-right;  
            if(diff <= 1 && diff >= -1){  
                depth = 1+(left > right?left : right);  
                return true;  
            }  
        }  
        return false;  
    }  
        public static void main(String[] args){  
            BinaryTreeNode root=new BinaryTreeNode();
            BinaryTreeNode node1=new BinaryTreeNode();
            BinaryTreeNode node2=new BinaryTreeNode();
            BinaryTreeNode node3=new BinaryTreeNode();
            BinaryTreeNode node4=new BinaryTreeNode();
            BinaryTreeNode node5=new BinaryTreeNode();
            BinaryTreeNode node6=new BinaryTreeNode();
            root.leftNode=node1;
            root.rightNode=node2;
            node1.leftNode=node3;
            node1.rightNode=node4;
            node2.rightNode=node5;
            node4.leftNode=node6;
            root.data=1;
            node1.data=2;
            node2.data=3;
            node3.data=4;
            node4.data=5;
            node5.data=6;
            node6.data=7;
            jiekou test = new jiekou();  
            System.out.println(test.treeDepth(root));
            System.out.println(test.isBalanced(root));
            System.out.println(test.isBalanced2(root));
        }
    }
   

在上面的代码中,我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子树结点之后,我们就可以根据它的左右子树的深度判断它时不时平衡的,并得到当前结点的深度。当最后遍历到树的根节点的时候,也就判断了整棵二叉树是不是平衡二叉树。

 

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
2018/07/11
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
【求助】想进大公司,但是算法不怎么好,该如何规划自己以后的学习?

我数学学得很糟糕,主要搞java,目前框架什么的都学完了,还有几个项目经验,所以来北京面试几家公司全都录用了,给了我一些信心;我想进一些知名企业,不求进BAT那种顶尖的,就想进一些像美...

上帝爱众生
2015/07/08
1K
14
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
2018/07/03
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nproc systemd on CentOS 7

Increasing nproc for processes launched by systemd on CentOS 7 Ask Question I have successfully increased the nofile and nproc value for the local users, but I couldn't find a p......

MtrS
今天
3
0
了解微信小程序下拉刷新功能

小程序提供了这个事件。 onPullDownRefresh() 监听用户下拉刷新事件。 如果要开启下拉刷新功能,要先到json配置: "enablePullDownRefresh":true 配置后下拉有反应了但是没有加载效果,在onP...

oixxan__
今天
2
0
springmvc java对象转json,上传下载(未完)拦截器Interceptor以及源码解析(未完待续)

package com.atguigu.my.controller;import java.util.Collection;import org.springframework.beans.factory.annotation.Autowired;import org.springframework.stereotype.Contr......

architect刘源源
今天
29
0
[日更-2019.5.24、25、26] Android系统中的Binder通信机制分析(一)--servicemanager

声明 其实对于Android系统Binder通信的机制早就有分析的想法,记得去年6、7月份Mr.Deng离职期间约定一起对其进行研究的,但因为我个人问题没能实施这个计划,留下些许遗憾... 最近,刚好在做...

Captain_小馬佩德罗
昨天
24
0
聊聊dubbo的DataStore

序 本文主要研究一下dubbo的DataStore DataStore dubbo-2.7.2/dubbo-common/src/main/java/org/apache/dubbo/common/store/DataStore.java @SPI("simple")public interface DataStore { ......

go4it
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部