104.二叉樹(shù)的最大深度

題目描述

給定一個(gè)二叉樹(shù) root ，返回其最大深度。

二叉樹(shù)的 最大深度 是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3

示例 2：

輸入：root = [1,null,2]
輸出：2

提示：

• 樹(shù)中節(jié)點(diǎn)的數(shù)量在 [0, 104] 區(qū)間內(nèi)。
• -100 <= Node.val <= 100

參考代碼

class solution {/*** 遞歸法*/public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}
}

111.二叉樹(shù)的最小深度

題目描述

給定一個(gè)二叉樹(shù)，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

**說(shuō)明：**葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：2

示例 2：

輸入：root = [2,null,3,null,4,null,5,null,6]
輸出：5

提示：

• 樹(shù)中節(jié)點(diǎn)數(shù)的范圍在 [0, 105] 內(nèi)
• -1000 <= Node.val <= 1000

參考代碼

class Solution {/*** 遞歸法，相比求MaxDepth要復(fù)雜點(diǎn)* 因?yàn)樽钚∩疃仁菑母?jié)點(diǎn)到最近**葉子節(jié)點(diǎn)**的最短路徑上的節(jié)點(diǎn)數(shù)量*/public int minDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = minDepth(root.left);int rightDepth = minDepth(root.right);if (root.left == null) {return rightDepth + 1;}if (root.right == null) {return leftDepth + 1;}// 左右結(jié)點(diǎn)都不為nullreturn Math.min(leftDepth, rightDepth) + 1;}
}

222.完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

題目描述

給你一棵 完全二叉樹(shù) 的根節(jié)點(diǎn) root ，求出該樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。

完全二叉樹(shù) 的定義如下：在完全二叉樹(shù)中，除了最底層節(jié)點(diǎn)可能沒(méi)填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2h 個(gè)節(jié)點(diǎn)。

示例 1：

輸入：root = [1,2,3,4,5,6]
輸出：6

示例 2：

輸入：root = []
輸出：0

示例 3：

輸入：root = [1]
輸出：1

提示：

• 樹(shù)中節(jié)點(diǎn)的數(shù)目范圍是[0, 5 * 104]
• 0 <= Node.val <= 5 * 104
• 題目數(shù)據(jù)保證輸入的樹(shù)是 完全二叉樹(shù)

參考代碼

class Solution {// 通用遞歸解法public int countNodes(TreeNode root) {if(root == null) {return 0;}return countNodes(root.left) + countNodes(root.right) + 1;}
}

Node root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}