## Java实现二叉树的深度计算 原

dev_chao

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

CSDN资讯
2018/10/02
0
0

AI科技大本营
2018/09/27
0
0

snailclimb
2018/05/08
0
0

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

2018/08/10
0
0

java通过ServerSocket与Socket实现通信

Blueeeeeee
28分钟前
4
0

4
0

badaoliumang

13
0

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

13
0
jquery--DOM操作基础

6
0