题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
104. 二叉树的深度
解法1 递归
思路为算出左右子树的深度，较大的一个加上根节点的1即为整个树的深度。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
//左右子树的深度
int left_depth = maxDepth(root.left);
int right_depth = maxDepth(root.right);
//加 1 是当前树的深度
return Math.max(left_depth, right_depth) + 1;
}
}
}
解法2 迭代
直接层序遍历，每遍历一层深度加一。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
int depth = 0;
if (root == null) {
return 0;
}
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode tmp = queue.poll();
if (tmp.left != null) {
queue.add(tmp.left);
}
if (tmp.right != null) {
queue.add(tmp.right);
}
}
depth++;
}
return depth;
}
}
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一颗高度平衡的二叉树定义为：一个二叉树的每个节点的左右两个子树的高度差的绝对值不超过1。
解法1 自顶向下的递归
按照题目要求，要满足
- 一个节点的左右子树的高度差不超过1
- 该节点的左右孩子也要满足第一点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
//空也为平衡二叉树
if (root == null) {
return true;
}
//满足分析的两个条件
return Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
//计算一个树的高度，也用递归实现
public int TreeDepth(TreeNode root) {
if (root == null) {
return -1;
}
int left_depth = TreeDepth(root.left);
int right_depth = TreeDepth(root.right);
return Math.max(left_depth, right_depth) + 1;
}
}
这种递归存在大量的冗余高度计算，计算一颗树的高度，是通过计算出其子树中较大的那个高度再 + 1 来实现的。在满足该题目要求 1 的时候没有问题，但当满足 2 时，深处的子树的高度多次重复计算。
解法2 自底向上的递归
主要思路是先判断子树是否平衡，如果平衡，再比较子树高度判断父节点是否平衡。
在leetcode评论区看到的简便写法。更容易理解。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution{
public boolean isBalanced(TreeNode root) {
//false时helper()为 -1 ，说明某一个节点不平衡
return helper(root)>=0;
}
public int helper(TreeNode root){
if(root == null){
return 0;
}
//左右子树高度
int l = helper(root.left);
int r = helper(root.right);
//-1说明不平衡
if(l==-1 || r==-1 || Math.abs(l-r)>1) return -1;
//平衡返回树的高度
return Math.max(l,r) +1;
}
}
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
111. 二叉树的最小深度
解法1 递归
与最大深度不同，最小深度要注意某一节点的左右子树是空的情况，如果一边为空，深度直接为另一边深度加1，如果两边为空，深度为1。
可以这样处理：当某个节点的左右子树其中一棵为null，给null的子树返回一个很大的深度，这样比较哪颗小的时候就会得到不是null的子树的深度。
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return minDepth0(root);
}
public int minDepth0(TreeNode root) {
if (root == null) {
return Integer.MAX_VALUE;
}
if (root.left == null && root.right == null) {
return 1;
}
int left_Min = minDepth0(root.left);
int right_Min = minDepth0(root.right);
return Math.min(left_Min, right_Min) + 1;
}
}
解法2 迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while (!queue.isEmpty()) {
depth++;
int n = queue.size();
for (int j = 0; j < n; j++) {
TreeNode tmp = queue.poll();
//如果当前节点的左右子树都为空，返回depth
if (tmp.left == null && tmp.right == null)
return depth;
if (tmp.left != null)
queue.add(tmp.left);
if (tmp.right != null)
queue.add(tmp.right);
}
}
return -1;
}
}
