Day15 | Part5
约 211 个字 93 行代码 预计阅读时间 2 分钟
层序遍历记录最后一行的第一个节点值即可(迭代), 也可以用for循环记录第一个 → 参考
| int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
if(!root) return 0;
q.push(root);
while(!q.empty()) {
root = q.front(); q.pop();
if(root->right) q.push(root->right); // 顺序不能变,若改变就找最右下角
if(root->left) q.push(root->left);
}
return root->val;
}
|
递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | void traverse(TreeNode* root, int& res, int& depth, int h) {
if(!root) return;
if(h > depth) {
depth = h;
res = root->val;
}
traverse(root->left, res, depth, h + 1);
traverse(root->right, res, depth, h + 1);
}
int findBottomLeftValue(TreeNode* root) {
int res = 0, depth = -1;
traverse(root, res, depth, 0);
return res;
}
|
递归: 不采用累加,而是目标值每次减去节点上的值,看最后为0么 → 回溯精简前参考
| bool hasPathSum(TreeNode* root, int targetSum) {
if(!root) return false;
if(root->val == targetSum && !root->left && !root->right) return true;
return hasPathSum(root->left, targetSum - root->val)
|| hasPathSum(root->right, targetSum - root->val);
}
|
迭代: 利用栈模拟,需要存该节点的指针和从头到该节点的路径和 → 利用pair
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | bool hasPathSum(TreeNode* root, int targetSum) {
stack<pair<TreeNode*, int>> st;
if(!root) return false;
st.push({root, root->val});
while(!st.empty()) {
auto node = st.top(); st.pop();
if(!node.first->left && !node.first->right
&& targetSum == node.second) return true;
if(node.first->left)
st.push({node.first->left, node.second + node.first->left->val});
if(node.first->right)
st.push({node.first->right, node.second + node.first->right->val});
}
return false;
}
|
找所有满足路径和的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | void dfs(vector<vector<int>>& res, vector<int> &path,
TreeNode* root, int sum) {
if(!root) return;
path.push_back(root->val);
if(!root->left && !root->right && sum == root->val) res.push_back(path);
dfs(res, path, root->left, sum - root->val);
dfs(res, path, root->right, sum - root->val);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res;
vector<int> path;
dfs(res, path, root, targetSum);
return res;
}
|
先从前序第一个节点开始,即头节点,之后在中序中进行切分,进行递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | TreeNode* build(vector<int>& pre, int preBegin, int preEnd,
vector<int>& in, int inBegin, int inEnd) {
if(preBegin > preEnd || inBegin > inEnd) return nullptr;
auto node = new TreeNode(pre[preBegin]);
int inRootIdx = inBegin;
while(node->val != in[inRootIdx]) inRootIdx ++;
node->left = build(pre, preBegin + 1, preBegin + inRootIdx - inBegin,
in, inBegin, inRootIdx - 1);
node->right = build(pre, preBegin + inRootIdx - inBegin + 1, preEnd,
in, inRootIdx + 1, inEnd);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
|
同理,先从后序最后一个节点开始,即头节点,之后在中序中递归切分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | TreeNode* build(vector<int>& in, int inBegin, int inEnd,
vector<int>& post, int postBegin, int postEnd) {
if(inBegin > inEnd || postBegin > postEnd) return nullptr;
auto node = new TreeNode(post[postEnd]);
int inRootIdx = inBegin;
while(node->val != in[inRootIdx]) inRootIdx ++;
node->left = build(in, inBegin, inRootIdx - 1,
post, postBegin, postBegin + inRootIdx - inBegin - 1);
node->right = build(in, inRootIdx + 1, inEnd,
post, postBegin + inRootIdx - inBegin, postEnd - 1);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return build(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}
|
