Day14 | Part4
约 137 个字 70 行代码 预计阅读时间 1 分钟
每一个节点的左右子树高度差的绝对值不超过1 → 高度VS深度
| int getDepth(TreeNode* node) {
if(!node) return 0;
return 1 + max(getDepth(node->left), getDepth(node->right));
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
int l = getDepth(root->left), r = getDepth(root->right);
return abs(l - r) <= 1
&& isBalanced(root->left)
&& isBalanced(root->right);
}
|
需要 回溯 即回退进入另一个路径,可作为函数参数进行传递,参考
递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | void traverse(vector<string>& res, TreeNode* root, string t) {
if(!root->left && !root->right) {
res.push_back(t);
return;
}
if(root->left)
traverse(res, root->left, t + "->" + to_string(root->left->val));
if(root->right)
traverse(res, root->right, t + "->" + to_string(root->right->val));
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if(!root) return res;
traverse(res, root, to_string(root->val));
return res;
}
|
迭代: 利用栈一个保存遍历的节点一个保存路径对应的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
stack<TreeNode*> st;
stack<string> path;
if(!root) return res;
st.push(root), path.push(to_string(root->val));
while(!st.empty()) {
auto node = st.top(); st.pop();
string p = path.top(); path.pop();
if(!node->left && !node->right) res.push_back(p);
if(node->left) {
st.push(node->left);
path.push(p + "->" + to_string(node->left->val));
}
if(node->right) {
st.push(node->right);
path.push(p + "->" + to_string(node->right->val));
}
}
return res;
}
|
节点A的左孩子不为空,且左孩子的左右孩子都为空,则A节点的左孩子为左叶子节点
递归:
| int sumOfLeftLeaves(TreeNode* root) {
if(!root) return 0;
if(!root->left && !root->right) return 0;
int l = sumOfLeftLeaves(root->left), r = sumOfLeftLeaves(root->right);
if(root->left && !root->left->left && !root->left->right)
l = root->left->val;
return l + r;
}
|
迭代:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | int sumOfLeftLeaves(TreeNode* root) {
int sum = 0;
stack<TreeNode*> st;
if(!root) return 0;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top(); st.pop();
if(node->left && !node->left->left && !node->left->right)
sum += node->left->val;
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
return sum;
}
|
