104 二叉樹的最大深度
給定一個(gè)二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
給定二叉樹 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
遞歸
- 入?yún)ⅲ焊?jié)點(diǎn)
- 遞歸終止，節(jié)點(diǎn)為null, return 0 ;
- 循環(huán)條件：當(dāng)前層級(jí)1+左右子節(jié)點(diǎn)的最大深度
- 返回最大深度
class Solution {
int[] deep = new int[2];
public int maxDepth(TreeNode root) {
if (root == null) return 0 ;
return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
迭代
- 層序遍歷的核心時(shí)一層一層遍歷，可使用通用模板，累加層級(jí)即可
class Solution {
public int maxDepth(TreeNode root) {
//層序遍歷
if(root == null) return 0;
int max = 0 ;
Deque<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()) {
int size = que.size();
++max;
for(int i = 0; i < size; ++i) {
TreeNode node = que.poll();
if(node.left!= null) que.offer(node.left);
if(node.right!= null) que.offer(node.right);
}
}
return max;
}
}
559.n叉樹的最大深度
給定一個(gè) N 叉樹，找到其最大深度。
最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)總數(shù)。
N 叉樹輸入按層序遍歷序列化表示，每組子節(jié)點(diǎn)由空值分隔（請參見示例）。
示例 1：
輸入：root = [1,null,3,2,4,null,5,6]
輸出：3
示例 2：
輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
輸出：5
提示：
樹的深度不會(huì)超過 1000 。
樹的節(jié)點(diǎn)數(shù)目位于 [0, 104] 之間。
遞歸
- 遞歸三部曲：入?yún)⒑头祷刂担ň植孔兞浚?，終止條件，循環(huán)條件
- 入?yún)ⅲ汗?jié)點(diǎn)
- 終止條件：節(jié)點(diǎn)為空
- 循環(huán)條件：每循環(huán)一層，深度+1
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0 ;
int maxDepth = 0 ;
if(root.children != null && root.children.size()>0){
for(Node child : root.children){
maxDepth = Math.max(maxDepth, maxDepth(child));
}
}
return maxDepth + 1;
}
}
迭代
- 參考二叉樹的最大深度，利用層序遍歷解決
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0 ;
int depth = 0;
Deque<Node> que = new LinkedList<Node>();
que.offer(root);
while(!que.isEmpty()){
depth++;
int size = que.size();
for(int i = 0; i < size; i++){
Node node = que.poll();
if(node.children!= null){
for(Node child : node.children){
que.offer(child);
}
}
}
}
return depth;
}
}
111.二叉樹的最小深度
給定一個(gè)二叉樹，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
**說明：**葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
遞歸
- 葉子節(jié)點(diǎn)，左右孩子都為空的節(jié)點(diǎn)才是葉子節(jié)點(diǎn)
- 入?yún)?每個(gè)節(jié)點(diǎn)，返回值：最小深度
- 終止條件：節(jié)點(diǎn)為空返回0
- 循環(huán)條件：
- 當(dāng)左子樹為空，最小深度在右子樹上
- 當(dāng)右子樹為空，最小深度在左子樹上
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0 ;
int minR = minDepth(root.right);
int minL = minDepth(root.left);
if(root.left == null) return 1 + minR ;
if(root.right == null) return 1 + minL ;
return Math.min(minR, minL) + 1 ;
}
}
迭代
- 思想同二叉樹的最大高度，區(qū)別在于當(dāng)左右子樹都為空時(shí)才時(shí)最小高度
- 當(dāng)?shù)玫阶钚「叨群?，不用再繼續(xù)遍歷樹，之后的高度肯定比當(dāng)前的高
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0 ;
Deque<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
int depth = Integer.MAX_VALUE;
int dep = 0 ;
while(!que.isEmpty()){
int size = que.size();
dep++;
for(int i = 0; i < size; i++){
TreeNode node = que.poll();
if(node.left!= null) que.offer(node.left);
if(node.right!= null) que.offer(node.right);
//重點(diǎn)：當(dāng)左右子樹為空時(shí)，計(jì)算一次最小高度并且之后不用再累加了
if(node.left == null && node.right == null){
return Math.min(depth, dep);
}
}
}
return depth;
}
}
222. 完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)
給你一棵 完全二叉樹 的根節(jié)點(diǎn) root ，求出該樹的節(jié)點(diǎn)個(gè)數(shù)。文章來源：http://www.zghlxwxcb.cn/news/detail-476333.html
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2h 個(gè)節(jié)點(diǎn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-476333.html
示例 1：
輸入：root = [1,2,3,4,5,6]
輸出：6
示例 2：
輸入：root = []
輸出：0
示例 3：
輸入：root = [1]
輸出：1
提示：
樹中節(jié)點(diǎn)的數(shù)目范圍是[0, 5 * 104]
0 <= Node.val <= 5 * 104
題目數(shù)據(jù)保證輸入的樹是 完全二叉樹
普通二叉樹遞歸
- 遞歸三部曲，不再重復(fù)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
普通二叉樹迭代
- 層序便利，累計(jì)元素個(gè)數(shù)
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int count = 0 ;
Deque<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
count += size;
for (int i = 0; i < size; i++) {
TreeNode node = que.poll();
if (node.left!= null) {
que.offer(node.left);
}
if (node.right!= null) {
que.offer(node.right);
}
}
}
return count;
}
}
完全二叉樹的遞歸
- 利用公式：完全二叉樹的高度為h，則節(jié)點(diǎn)個(gè)數(shù)=2^h -1
- 分別求出左右字?jǐn)?shù)的高度，利用公式計(jì)算
- 當(dāng)左右子樹都存在時(shí)，高度+1
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int depL = 1 ,depR = 1;
TreeNode left = root.left;
while(left != null){
depL++;
left = left.left;
}
TreeNode right = root.right;
while(right!= null){
depR++;
right = right.right;
}
if(depL == depR) {
return (1<<depL) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
總結(jié)
- 遞歸三部曲：參數(shù)和返回值、終止條件、單層循環(huán)條件
- 層序遍歷模板：隊(duì)列、隊(duì)列大小、循環(huán)隊(duì)列大小
- 完全二叉樹性質(zhì)：節(jié)點(diǎn)=2^h -1
到了這里，關(guān)于算法學(xué)習(xí)day16的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
