513. 找树左下角的值
1.前序遍历
思路
题目的要求是先是最底层最左边的节点的值，我们使用前序遍历可以保证是最左边的值，通过深度变化时对节点更新，可以保证是最底层的值。
实现
点击查看代码
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
traversal(root,1);
return result;
}
int max = 0;
int result = 0;
void traversal(TreeNode* root, int depth){
if(depth > max){
max = depth;
result = root->val;
}
if(root->left)traversal(root->left,depth+1);
if(root->right)traversal(root->right,depth+1);
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
112. 路径总和
1.前序遍历
思路
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。
实现
点击查看代码
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
return isexsit(root,targetSum);
}
bool isexsit(TreeNode* root, int count){
if(root == nullptr)return false;
count -= root->val;
if(root->left == nullptr && root->right == nullptr && count == 0){
return true;
}
if(root->left){
if(isexsit(root->left,count))return true;
}
if(root->right){
if(isexsit(root->right,count))return true;
}
return false;
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
113. 路径总和 II
1.前序遍历
思路
使用一个栈记录路径
实现
点击查看代码
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return result;
vector<int> path;
traversal(root,path,0,targetSum);
return result;
}
vector<vector<int>> result;
void traversal(TreeNode* root, vector<int> path,int sum,int& targetSum){
sum += root->val;
path.push_back(root->val);
if(root->left == nullptr && root->right == nullptr && sum == targetSum){
result.push_back(path);
}
if(root->left)traversal(root->left,path,sum,targetSum);
if(root->right)traversal(root->right,path,sum,targetSum);
}
};
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
105. 从前序与中序遍历序列构造二叉树
思路
- 如果写过前序和后序遍历的迭代法的话，会理解这两种写法的写法是类似的，105和106本质上没有区别，只是一个同类型题的变化。
- 这道题的写法是一种固定题型，需要记住。主要思路为通过前序遍历确定中间节点，在中序遍历
找到中间节点，确定左右子树的大小，再对前序遍历切割。前序->中序->前序。
- 如果头结点为空节点，返回空指针。
- 找到前序遍历的第一个值，将其定为中间节点。
- 如果数组中只有一个节点，将其返回
- 在中序遍历中找出中间节点的位置
- 对中序和前序遍历进行切割
- 递归处理左右子树区间。
实现
点击查看代码
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return traversal(preorder,inorder);
}
TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){
if(inorder.size() == 0)return nullptr;
int rootValue = preorder[0];
TreeNode* root = new TreeNode(rootValue);
if(preorder.size() == 1)return root;
int index = 0;
for(index = 0; index < inorder.size(); index++){
if(inorder[index] == rootValue)break;
}
vector<int> leftinorder(inorder.begin(),inorder.begin()+index);
vector<int> rightinorder(inorder.begin()+index+1,inorder.end());
vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+1+leftinorder.size());
vector<int> rightpreorder(preorder.begin()+1+leftinorder.size(),preorder.end());
root-> left = traversal(leftpreorder,leftinorder);
root-> right = traversal(rightpreorder,rightinorder);
return root;
}
};
复杂度分析
- 时间复杂度：O(n)，因为对每一个节点都要进行处理。
- 空间复杂度：O(n^2)