[LeetCode] 二叉树 III — 110#平衡二叉树 | 257#二叉树的所有路径 | 404#左叶子之和 | 222#完全二叉树的节点个数
二叉树的遍历与性质
- 110# 平衡二叉树
- 257# 二叉树的所有路径
- 404# 左叶子之和
- 222# 完全二叉树的节点个数（利用完全二叉树的性质）
前置知识&遍历方法汇总移步：先前博文
110# 平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树
平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false示例 3：
输入：root = [] 输出：true提示：
- 树中的节点数在范围
[0, 5000]内-10^4 <= Node.val <= 10^4
求高度：后序遍历
// 迭代法
// O(n) 0ms; O(n) 22.62MB
class Solution {
public:
int getHeight(TreeNode* root) {
if (root==nullptr) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) return -1;
return max(leftHeight, rightHeight) + 1;
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
迭代法：定义一个函数求最大深度（即最大高度）（层序遍历不能直接用来求高度）
// 迭代法
// O(n^2) 11ms; O(n) 33.38MB
class Solution {
public:
int getDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> que;
if (root == nullptr) return depth;
que.push(root);
while (!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode *cur = que.front();
que.pop();
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return depth;
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) return true;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
if (abs(getDepth(cur->left) - getDepth(cur->right)) > 1) return false;
if (cur->left) st.push(cur->left);
if (cur->right) st.push(cur->right);
}
return true;
}
};
257# 二叉树的所有路径
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]示例 2：
输入：root = [1] 输出：["1"]提示：
- 树中节点的数目在范围
[1, 100]内-100 <= Node.val <= 100
前序遍历
// 递归法
// O(n^2) 0ms; O(n^2) 17.07MB
class Solution {
public:
void traversal(TreeNode* root, string path, vector<string>& result) { // path非引用，从而达到回溯的效果
path += to_string(root->val);
if (root->left == nullptr && root-> right == nullptr) {
result.push_back(path);
return;
}
if (root->left) traversal(root->left, path + "->", result);
if (root->right) traversal(root->right, path + "->", result);
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == nullptr) return result;
traversal(root, path, result);
return result;
}
};
字符串拼接的时间复杂度为O(k)（k为字符串长度）
// 迭代法（前序遍历）
// O(n^2) 0ms; O(n^2) 16.2MB
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (root == nullptr) return result;
stack<TreeNode*> treeSt;
stack<string> pathSt; // 存储treeSt中节点对应的遍历路径
treeSt.push(root);
pathSt.push(to_string(root->val));
while (!treeSt.empty()) {
TreeNode* cur = treeSt.top();
treeSt.pop();
string path = pathSt.top();
pathSt.pop();
if (cur->left == nullptr && cur->right == nullptr) result.push_back(path);
if (cur->right) {
treeSt.push(cur->right);
pathSt.push(path + "->" + to_string(cur->right->val));
}
if (cur->left) {
treeSt.push(cur->left);
pathSt.push(path + "->" + to_string(cur->left->val));
}
}
return result;
}
};
404# 左叶子之和
给定二叉树的根节点
root，返回所有左叶子之和。示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24示例 2:
输入: root = [1] 输出: 0提示:
- 节点数在
[1, 1000]范围内-1000 <= Node.val <= 1000
注意，只有当前遍历的节点是父节点，才能判断一个节点（子节点）是不是左叶子
// 递归法
// O(n) 0ms; O(n) 15.93MB
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int leftSum = 0;
if (root->left) {
if (root->left->left == nullptr && root->left->right == nullptr) leftSum += root->left->val;
else leftSum += sumOfLeftLeaves(root->left);
}
if (root->right) leftSum += sumOfLeftLeaves(root->right);
return leftSum;
}
};
// 迭代法（前序遍历）
// O(n) 0ms; O(n) 16.1MB
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int leftSum = 0;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
if (cur->right) st.push(cur->right);
if (cur->left) {
if (cur->left->left == nullptr && cur->left->right == nullptr) leftSum += cur->left->val;
else st.push(cur->left);
}
}
return leftSum;
}
};
222# 完全二叉树的节点个数（利用完全二叉树的性质）
给你一棵 完全二叉树 的根节点
root，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h层（从第 0 层开始），则该层包含1~ 2^h个节点。示例 1：
输入：root = [1,2,3,4,5,6] 输出：6示例 2：
输入：root = [] 输出：0示例 3：
输入：root = [1] 输出：1提示：
- 树中节点的数目范围是
[0, 5 * 104]0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
不利用完全二叉树解题的递归法和迭代法复杂度为 O(n); O(n)
利用完全二叉树在递归过程中一定有子树为满二叉树，且满二叉树节点个数为2^k-1的性质
因此在递归过程中判断其子树是否为满二叉树，是则直接计算节点数量，不是则继续递归
判断满二叉树：向左遍历的深度 = 向右遍历的深度
// 递归法--利用完全二叉树与满二叉树性质
// O(logn * logn) 0ms; O(logn) 30.63MB
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode *leftNode = root->left, *rightNode = root->right;
int leftDepth = 0, rightDepth = 0;
while (leftNode) {
leftDepth++;
leftNode = leftNode->left;
}
while (rightDepth) {
rightDepth++;
rightNode = rightNode->right;
}
if (leftDepth == rightDepth) return 1 << (leftDepth + 1) - 1; // leftDepth从0开始
else return 1 + countNodes(root->left) + countNodes(root->right);
}
};
递归深度在最坏情况下为 O(h) 即 O(logn)
本文参考 LeetCode官方题解 及 代码随想录