104.二叉樹的最大深度??
題目鏈接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
二叉樹節(jié)點的深度：指從根節(jié)點到該節(jié)點的最長簡單路徑邊的條數(shù)或者節(jié)點數(shù)（取決于深度從0開始還是從1開始）
二叉樹節(jié)點的高度：指從該節(jié)點到葉子節(jié)點的最長簡單路徑邊的條數(shù)或者節(jié)點數(shù)（取決于高度從0開始還是從1開始）
后序遍歷（左右中）來計算樹的高度：
1.確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)就是傳入樹的根節(jié)點，返回就返回這棵樹的深度，所以返回值為int類型。
2.確定終止條件：如果為空節(jié)點的話，就返回0，表示高度為0。
3.確定單層遞歸的邏輯：先求它的左子樹的深度，再求右子樹的深度，最后取左右深度最大的數(shù)值 再+1 （加1是因為算上當前中間節(jié)點）就是目前節(jié)點為根節(jié)點的樹的深度。
前序（中左右）方法：充分表現(xiàn)出求深度回溯的過程
559. n叉樹的最大深度
題目鏈接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
for (Node tmpNode : node. children){
? ? ? ? ? ? depth = Math.max(depth, getDepth(tmpNode));
? ? ? ? ? ? //超時：if (getDepth(tmpNode)>depth){depth = getDepth(tmpNode);}
? ? }
?111.二叉樹的最小深度
題目鏈接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/
錯誤解法：
int?leftDepth?=?getDepth(node->left);
int?rightDepth?=?getDepth(node->right);
int result = 1?+?min(leftDepth,?rightDepth);
造成的錯誤：
正確解法：如果左子樹為空，右子樹不為空，說明最小深度是 1 + 右子樹的深度。反之，右子樹為空，左子樹不為空，最小深度是 1 + 左子樹的深度。 最后如果左右子樹都不為空，返回左右子樹深度最小值 + 1 。
解法2: 可以用層序遍歷
?222.完全二叉樹的節(jié)點個數(shù)
題目鏈接：https://leetcode.cn/problems/count-complete-tree-nodes/
解法1: 層序遍歷
迭代法，二叉樹：層序遍歷登場！?(opens new window)遍歷模板稍稍修改一下，記錄遍歷的節(jié)點數(shù)量就可以了。
解法2: 遞歸遍歷
遞歸遍歷的順序依然是后序（左右中）
#完全二叉樹
完全二叉樹中，除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~?2^(h-1) ?個節(jié)點。
完全二叉樹只有兩種情況，情況一：就是滿二叉樹，情況二：最后一層葉子節(jié)點沒有滿。
1. 對于情況一，可以直接用 2^樹深度 - 1 來計算，注意這里根節(jié)點深度為1。
2.對于情況二，分別遞歸左孩子，和右孩子，遞歸到某一深度一定會有左孩子或者右孩子為滿二叉樹，然后依然可以按照情況1來計算。
如何去判斷一個左子樹或者右子樹是不是滿二叉樹呢？
在完全二叉樹中，如果遞歸向左遍歷的深度等于遞歸向右遍歷的深度，那說明就是滿二叉樹。
if (root==null) return0;
1.?滿二叉樹：可以直接用 2^樹深度 - 1 來計算
TreeNodeleft=root.left;
TreeNoderight=root.right;
int leftDepth=0, rightDepth=0;// 這里初始為0是有目的的，為了下面求指數(shù)方便
while (left!=null) {// 求左子樹深度
????left = left. left;
????leftDepth++;}
while (right!=null) {// 求右子樹深度
????right=right.right;
????rightDepth++;}
if (leftDepth==rightDepth) {
????return(2<<leftDepth)-1; // 注意(2<<1) 相當于2^2，所以leftDepth初始為0}
2. 非滿二叉樹：分別遞歸其左右孩子，直到遇到滿二叉樹為止，用公式計算這個子樹（滿二叉樹）的節(jié)點數(shù)量
int leftTreeNum=countNodes(root.left);// 左
int rightTreeNum=countNodes(root.right);// 右
int result=leftTreeNum+rightTreeNum+1;// 中
精簡之后：
return countNodes(root.left)+countNodes(root.right)+1;
