題目描述
給定一個(gè)二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
104. 二叉樹的深度
解法1 遞歸
思路為算出左右子樹的深度，較大的一個(gè)加上根節(jié)點(diǎn)的1即為整個(gè)樹的深度。
/**
* 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 是當(dāng)前樹的深度
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;
}
}
題目描述
給定一個(gè)二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一顆高度平衡的二叉樹定義為：一個(gè)二叉樹的每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1。
解法1 自頂向下的遞歸
按照題目要求，要滿足
- 一個(gè)節(jié)點(diǎn)的左右子樹的高度差不超過1
- 該節(jié)點(diǎn)的左右孩子也要滿足第一點(diǎn)
/**
* 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;
}
//滿足分析的兩個(gè)條件
return Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
//計(jì)算一個(gè)樹的高度，也用遞歸實(shí)現(xiàn)
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;
}
}
這種遞歸存在大量的冗余高度計(jì)算，計(jì)算一顆樹的高度，是通過計(jì)算出其子樹中較大的那個(gè)高度再 + 1 來實(shí)現(xiàn)的。在滿足該題目要求 1 的時(shí)候沒有問題，但當(dāng)滿足 2 時(shí)，深處的子樹的高度多次重復(fù)計(jì)算。
解法2 自底向上的遞歸
主要思路是先判斷子樹是否平衡，如果平衡，再比較子樹高度判斷父節(jié)點(diǎn)是否平衡。
在leetcode評(píng)論區(qū)看到的簡(jiǎn)便寫法。更容易理解。
/**
* 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時(shí)helper()為 -1 ，說明某一個(gè)節(jié)點(diǎn)不平衡
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;
}
}
題目描述
給定一個(gè)二叉樹，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
111. 二叉樹的最小深度
解法1 遞歸
與最大深度不同，最小深度要注意某一節(jié)點(diǎn)的左右子樹是空的情況，如果一邊為空，深度直接為另一邊深度加1，如果兩邊為空，深度為1。
可以這樣處理：當(dāng)某個(gè)節(jié)點(diǎn)的左右子樹其中一棵為null，給null的子樹返回一個(gè)很大的深度，這樣比較哪顆小的時(shí)候就會(huì)得到不是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();
//如果當(dāng)前節(jié)點(diǎn)的左右子樹都為空，返回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;
}
}
