二叉树的深度

题目描述

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

分析

递归:二叉树的深度为其左右子树深度中大的那个数加1。两行代码搞定。

迭代:利用层序遍历,算出总共有几层,就是二叉树的深度。

代码:

递归:

public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}
}

迭代:

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<TreeNode>();
int count = 0;
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
TreeNode node = q.poll();
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
count++;
}
return count;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :