建设银行租房网站首页,网站开发外包公司坑,会泽住房和城乡建设局网站,深度网营销型网站建设文章目录二叉树9. 二叉树的最大深度10. 二叉树的最小深度11. 完全二叉树的节点个数12. 平衡二叉树二叉树
9. 二叉树的最大深度
104. 二叉树的最大深度 思路1#xff1a; 递归找左右子树的最大深度#xff0c;选择最深的 1#xff08;即加上当前层#xff09;。 class So…
文章目录二叉树9. 二叉树的最大深度10. 二叉树的最小深度11. 完全二叉树的节点个数12. 平衡二叉树二叉树
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;queueTreeNode * 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;queueTreeNode * 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. 完全二叉树的节点个数 思路 满二叉树的节点数目等于 2depth−12^{depth} - 12depth−1 利用该条件来避免遍历整个满二叉树只需要遍历其最左最右两分支的深度即可O(logn)O(logn)O(logn)。遍历二叉树的递归层数 O(logn)O(logn)O(logn) 。时间复杂度是 O(logn∗logn)O(logn*logn)O(logn∗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;stackTreeNode * 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;stackTreeNode * 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;}
};
