文档章节

Java实现二叉树的深度计算

dev_chao
 dev_chao
发布于 2017/03/26 16:33
字数 458
阅读 154
收藏 0

尝试不同方法求二叉树的深度:

1.depth1,递归计算二叉树的深度,根结点的深度=max(左子树的深度,右子树的深度) + 1。

2.depth2,访问左结点,如有右结点则压栈1,同时把右结点的深度压栈2,没有左结点时表示该次遍历完成,记录深度;从栈1取出结点,栈2取出该结点的深度,再次遍历。

3.depth3,利用层序遍历的思想,每完成一层的遍历就给一个标记。

package com.devchao.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

	public static void main(String[] args) {
		
		Node n15 = new Node(15, null, null);
		Node n14 = new Node(14, n15, null);
		Node n13 = new Node(13, null, n14);
		Node n12 = new Node(12, n13, null);
		Node n11 = new Node(11, null, n12);
		
		Node n5 = new Node(5, null, null);
		Node n6 = new Node(6, null, null);
		Node n8 = new Node(8, null, null);
		Node n9 = new Node(9, n11, null);
		Node n10 = new Node(10, null, null);
		Node n7 = new Node(7, n8, null);
		Node n4 = new Node(4, n6, n7);
		Node n3 = new Node(3, null, n5);
		Node n2 = new Node(2, n9, n10);
		Node n1 = new Node(1, n3, n4);
		Node root = new Node(0, n1, n2);
		System.out.println(depth3(root));
	}
	
	public static int depth1(Node root){
		int dep1 = 1, dep2 = 1;
		if(root.left != null) {
			dep1 = dep1 + depth1(root.left);
		}
		if(root.right != null) {
			dep2 = dep2 + depth1(root.right);
		}
		
		System.out.println(root.data + " " + dep1 + " " + dep2);
		return dep1 >= dep2 ? dep1 : dep2;
	}
	
	public static int depth2(Node root){
		int dep = 1, tempDep = 1;
		Stack<Node> q = new Stack<Node>();
		Stack<Integer> dq = new Stack<Integer>();
		Node node = root;
		
		while(node != null || !q.isEmpty()) {
			if(node == null) {
				node = q.pop();
				dep = dep < tempDep ? tempDep : dep;
				tempDep = dq.pop();
			}
			if(node.right != null) {
				dq.add(tempDep + 1);
				q.add(node.right);
			}
			
			if(node.left != null) {
				tempDep = tempDep + 1;
			} 
			node = node.left;
		}
		return dep;
	}
	
	public static int depth3(Node root){
		int dep = 0, tempTag = 0;
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		
		Queue<Integer> tagQueue = new LinkedList<>();
		tagQueue.add(1);
		
		while(!queue.isEmpty()) {
			root = queue.poll();
			if(root.left != null) {
				queue.add(root.left);
				tagQueue.add(0);
			}
			
			if(root.right != null) {
				queue.add(root.right);
				tagQueue.add(0);
			}
			
			tempTag = tagQueue.poll();
			if(tempTag == 1) {
				dep = dep + 1;
				if(!tagQueue.isEmpty()) {
					tagQueue.remove();
					tagQueue.add(1);
				}
			}
		}
		return dep;
	}
	
	
	
	static class Node {

		public int data;
		public Node left;
		public Node right;

		public Node(int data, Node left, Node right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}
}

 

© 著作权归作者所有

dev_chao
粉丝 5
博文 36
码字总数 11158
作品 0
广州
私信 提问
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
阿里面试必问之,手写 Java 二叉树

阿里面试 现在很多公司在招聘开发岗位的时候,都会事先在招聘信息中注明面试者应当具备的知识技能,而且在面试的过程中,有部分对于技能掌握程度有严格要求的公司还会要求面试者手写代码,这...

Java-飞鱼
09/05
87
0
1-玩转数据结构-欢迎学习数据结构

欢迎大家学习新课程: 玩转数据结构 为什么要学习数据结构? 数据结构是所有计算机专业的同学必学的课程 数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者...

天涯明月笙
2018/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
28分钟前
4
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
4
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
13
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
13
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部