104.二叉樹的最大深度?
思路：
層序遍歷，每一層深度加1，遍歷完所有節(jié)點(diǎn)。返回深度。
看視頻后：
深度：指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于深度從0開始還是從1開始）從上往下，所以用前序
高度：從該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于高度從0開始還是從1開始）從下往上，所以用后序
根節(jié)點(diǎn)的高度就是二叉樹的最大深度,因此本題可以使用后序。其他節(jié)點(diǎn)的深度=(最大高度（根節(jié)點(diǎn)）-高度（該節(jié)點(diǎn)）+1）
高度后序遍歷：
int?maxDepth(TreeNode*?root)?{
????????if(root==NULL)
????????????return?0;
????????int?leftHeight?=?maxDepth(root->left);
????????int?rightHeight?=?maxDepth(root->right);
????????int?Depth=(1+max(leftHeight,rightHeight));
????????return?Depth;
????}
深度前序遍歷：
先判斷節(jié)點(diǎn)，如果節(jié)點(diǎn)為空則返回（邊界條件）。設(shè)立變量result，每次比較節(jié)點(diǎn)和它的深度，記錄最大值（中）。如果左節(jié)點(diǎn)存在，深度加1，并對左節(jié)點(diǎn)進(jìn)行遍歷，結(jié)束后回退1（左）。同樣對右節(jié)點(diǎn)進(jìn)行操作。
public：
int result=0;
void?getDepth(TreeNode*?node,?int?depth)
????{
????????if(node==NULL)
????????????return;
????????result=depth?>?result???depth?:?result;
????????if(node->left)
????????{
????????????depth++;
????????????getDepth(node->left,depth);
????????????depth--;
????????}
????????if(node->right)
????????{
????????????depth++;
????????????getDepth(node->right,depth);
????????????depth--;
????????}
????}
完成了559號題目。
?111.二叉樹的最小深度?
思路：
1.層序遍歷，每一層深度加1。在左節(jié)點(diǎn)和右節(jié)點(diǎn)push進(jìn)queue之前，增加判斷：左節(jié)點(diǎn)和右節(jié)點(diǎn)都為null，則返回深度+1；其他相同。
2. 類似上一題最大深度，但只改成min并不成功；
看視頻后：
需要考慮左子樹為空右子樹不為空或者左子樹不為空右子樹為空的情況。
222.完全二叉樹的節(jié)點(diǎn)個數(shù)
思路：
1.使用層序遍歷把所有節(jié)點(diǎn)遍歷，每遍歷一個節(jié)點(diǎn) sum++
2.設(shè)置public變量sum,在函數(shù)里如果root==null則返回，否則sum++,然后對左右節(jié)點(diǎn)進(jìn)行遞歸。最后return sum。
看視頻后：
由于是完全二叉樹，要根據(jù)完全二叉樹的特性做題。
在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。
因此，除了最后一層，其他都是滿二叉樹。滿二叉樹的元素個數(shù)為2^depth-1.如果以節(jié)點(diǎn)為對稱軸，滿二叉樹的外圍的左節(jié)點(diǎn)和右節(jié)點(diǎn)長度相等。因此我們可以判斷二叉樹是否為滿二叉樹，如果是，則為2^leftdepth-1。如果不是，右節(jié)點(diǎn)長度則比左節(jié)點(diǎn)長度小1，元素個數(shù)為2^rightdepth-1.
最后再合并左右子樹的個數(shù)加節(jié)點(diǎn)1.
int?compare(TreeNode?*Node)
????{
????????int?leftDepth=1;
????????int?rightDepth=1;
????????TreeNode*?tempNode=Node;
????????while(Node->left!=NULL)
????????{
????????????Node=Node->left;
????????????leftDepth++;?
????????}
????????Node=tempNode;
????????while(Node->right!=NULL)
????????{
????????????Node=Node->right;
????????????rightDepth++;
????????}
????????if(leftDepth==rightDepth)
????????????return?2^leftDepth-1;
????????return?2^rightDepth-1;?
????}
????int?countNodes(TreeNode*?root)?{
????????if(root==NULL)
????????????return?0;
????????int?leftCount=countNodes(root->left);
????????int?rightCount=countNodes(root->right);
????????int?count=leftCount+rightCount+1;
????????return?count;
????}
