随想录二刷Day17——二叉树

二叉树

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： 递归法
要注意只有一个子节点的情况不能统计深度，因为它不是叶子节点。深度是指根节点到叶子节点的距离。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;// 下面的两个判断避免了非叶子节点的情况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：
利用迭代法层序遍历，遇到第一个叶子节点返回深度。

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. 完全二叉树的节点个数

222. 完全二叉树的节点个数

思路：
满二叉树的节点数目等于 $2^{depth}-1$ ，利用该条件来避免遍历整个满二叉树，只需要遍历其最左最右两分支的深度即可（$O(logn)$）。遍历二叉树的递归层数 $O(logn)$ 。时间复杂度是 $O(logn\ast logn)$

class Solution {
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;// 利用满二叉树的特性优化时间复杂度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： 递归
后序遍历统计左右子树的高度，比较左右子树高度是否满足条件。

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; // 如果已经找到不满足底子树，就没必要再遍历了。剪枝return max(leftDepth, rightDepth) + 1;}
};

思路2： 迭代法
用栈模拟递归实现后续遍历统计二叉树深度。
再先序遍历判断左右子树深度是否满足条件。
这里没法剪枝，复杂度并不优秀。

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;}
};