二叉树的深度（递归和非递归）

发表于 更新于 分类于 阅读次数：

原题

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

递归方法

用递归实现，先求其左子树的深度和右子树的深度，递归出口为当前节点为null。然后在比较左右大小，选择最大的一边的值返回。

非递归方法

遍历每一层的节点，层数用level记录。用cur和last表示当前层处理过的节点和最后一个节点。

实现和测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package com.geelaro.tree;

import java.util.LinkedList;

public class BinaryTree {
	/** 递归方法 **/
	static int findDeep(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = findDeep(root.left);
		int right = findDeep(root.right);
		// System.out.println("left=" + left + ", right=" + right);
		return left > right ? left + 1 : right + 1;

	}

	/** 非递归方法 **/
	static int findDeep2(TreeNode root) {
		if (root == null) {
			return 0;
		}
		TreeNode current = null;

		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();

		queue.offer(root);

		int level = 0;
		int cur, last;

		while (!queue.isEmpty()) {
			cur = 0;// 记录当前层节点个数
			last = queue.size();// 当前层节点的个数

			while (cur < last) {
				current = queue.poll(); // 把第一个元素提出来
				cur++;

				// 把当前的左右节点入队
				if (current.left != null) {
					queue.offer(current.left);
				}
				if (current.right != null) {
					queue.offer(current.right);
				}
			}
			level++;// 每遍历一层，level+1
		}

		return level;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		TreeNode left = new TreeNode(2);
		TreeNode right = new TreeNode(3);
		TreeNode right2 = new TreeNode(4);
		// 创建树
		root.left = left;
		root.right = right;
		right.left = right2;

		System.out.println("deep is " + findDeep(root));
		System.out.println("deep2 is " + findDeep2(root));
	}

}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val) {
		this.val = val;
	}

}