JZ55 二叉树的深度
描述
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度,根节点的深度视为 1 。
方法1 递归
思路:
最大深度是所有叶子节点的深度的最大值,深度是指树的根节点到任一叶子节点路径上节点的数量,因此从根节点每次往下一层深度就会加1。因此二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值。而每个子树我们都可以看成一个根节点,继续用上述方法求的深度,于是我们可以对这个问题划为子问题,利用递归来解决: 终止条件: 当进入叶子节点后,再进入子节点,即为空,没有深度可言,返回0. 返回值: 每一级按照上述公式,返回两边子树深度的最大值加上本级的深度,即加1.
代码
Java
if(root == null) { return 0; } else { return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1; }
方法2 层次遍历
思路
必须是一层一层的,那一层就是一个深度,有的层可能会很多节点,有的层如根节点或者最远的叶子节点,只有一个节点,但是不管多少个节点,它们都是一层。因此我们可以使用层次遍历,二叉树的层次遍历就是从上到下按层遍历,每层从左到右,我们只要每层统计层数即是深度。
代码
Java
package esay.JZ55二叉树的深度;import java.util.LinkedList;import java.util.Queue;class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}public class Solution { public int TreeDepth(TreeNode root) { //方法1 /*if(root == null) { return 0; } else { return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1; }*/ if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int res = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res++; } return res; }}
还没有评论,来说两句吧...