二叉樹

9. 二叉樹的最大深度

104. 二叉樹的最大深度

思路1：
遞歸找左右子樹的最大深度，選擇最深的 + 1（即加上當前層）。

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

思路2：
利用隊列層序遍歷二叉樹，找到最大深度

class Solution {
public:int maxDepth(TreeNode* root) {int depth = 0;if (root == NULL) return depth;queue<TreeNode *> que;que.push(root);while (!que.empty()) {int size = que.size();depth++;while (size--) {TreeNode *cur = que.front(); que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

10. 二叉樹的最小深度

111. 二叉樹的最小深度

思路1： 遞歸法
要注意只有一個子節(jié)點的情況不能統(tǒng)計深度，因為它不是葉子節(jié)點。深度是指根節(jié)點到葉子節(jié)點的距離。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;// 下面的兩個判斷避免了非葉子節(jié)點的情況if (!root->left && root->right) return minDepth(root->right) + 1;if (root->left && !root->right) return minDepth(root->left) + 1;return min(minDepth(root->left), minDepth(root->right)) + 1;}
};

思路2：
利用迭代法層序遍歷，遇到第一個葉子節(jié)點返回深度。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;queue<TreeNode *> que;int depth = 0;que.push(root);while (!que.empty()) {depth++;int size = que.size();while (size--) {TreeNode *cur = que.front(); que.pop();if (!cur->left && !cur->right) return depth;if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

11. 完全二叉樹的節(jié)點個數(shù)

222. 完全二叉樹的節(jié)點個數(shù)

思路：
滿二叉樹的節(jié)點數(shù)目等于 $2^{depth}?1$ ，利用該條件來避免遍歷整個滿二叉樹，只需要遍歷其最左最右兩分支的深度即可（$O(logn)$）。遍歷二叉樹的遞歸層數(shù) $O(logn)$ 。時間復雜度是 $O(logn?logn)$

class Solution {
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;// 利用滿二叉樹的特性優(yōu)化時間復雜度TreeNode *curL = root->left;TreeNode *curR = root->right;int depthL = 0;int depthR = 0;while (curL != NULL) {curL = curL->left;depthL++;}while (curR != NULL) {curR = curR->right;depthR++;}if (depthL == depthR) return (2 << depthL) - 1;return countNodes(root->left) + countNodes(root->right) + 1;}
};

12. 平衡二叉樹

110. 平衡二叉樹

思路1： 遞歸
后序遍歷統(tǒng)計左右子樹的高度，比較左右子樹高度是否滿足條件。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;return getHigh(root) == -1 ? false : true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;int leftDepth = getHigh(root->left);if (leftDepth == -1) return -1;int rightDepth = getHigh(root->right);if (rightDepth == -1) return -1;if (abs(leftDepth - rightDepth) > 1) return -1; // 如果已經(jīng)找到不滿足底子樹，就沒必要再遍歷了。剪枝return max(leftDepth, rightDepth) + 1;}
};

思路2： 迭代法
用棧模擬遞歸實現(xiàn)后續(xù)遍歷統(tǒng)計二叉樹深度。
再先序遍歷判斷左右子樹深度是否滿足條件。
這里沒法剪枝，復雜度并不優(yōu)秀。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;stack<TreeNode *> stk;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (abs(getHigh(cur->left) - getHigh(cur->right)) > 1) return false;if (cur->right) stk.push(cur->right);if (cur->left) stk.push(cur->left);}return true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;stack<TreeNode *> stk;int depth = 0, result = 0;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (cur) { // 后序遍歷：左右中stk.push(cur); // 中stk.push(NULL);depth++;if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top(); stk.pop();depth--; // 回溯}result = result > depth ? result : depth;}return result;}
};