513.找树左下角的值
文章链接:https://programmercarl.com/0513.找树左下角的值.html
题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/description/
要点:不管是前中后序遍历,左节点总是先比右节点先遍历,所以只要找到深度最大的叶子节点,即找到最左下角的值
class Solution {
public:
int maxDepth=INT_MIN;
int result;
void traversal(TreeNode* root,int depth){
if(root->left==NULL&&root->right==NULL){
if(depth>maxDepth){
maxDepth=depth;
result=root->val;
}
return;
}
if(root->left) traversal(root->left,depth+1);
if(root->right) traversal(root->right,depth+1);
}
int findBottomLeftValue(TreeNode* root) {
traversal(root,1);
return result;
}
};
递归的方法:
class Solution {
public:
//迭代:层序遍历
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
int result;
if(root!=NULL) que.push(root);
while(!que.empty()){
int size=que.size();
for(int i=0;i<size;i++){
TreeNode* node=que.front();
que.pop();
if(i==0) result=node->val;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
}
return result;
}
};
路径总和
文章链接:https://programmercarl.com/0112.路径总和.html
题目链接:https://leetcode.cn/problems/path-sum/description/
class Solution {
public:
bool getPathSum(TreeNode* root,int sum,int targetSum){
sum+=root->val;
if(root->left==NULL&&root->right==NULL) return sum==targetSum;
if(root->left&&getPathSum(root->left,sum,targetSum)) return true;
if(root->right&&getPathSum(root->right,sum,targetSum)) return true;
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL) return false;
return getPathSum(root,0,targetSum);
}
};
路径总和II
class Solution {
public:
vector<vector<int>> result;
void func(TreeNode* root,vector<int> path,int sum,int targetSum){
path.push_back(root->val);
sum+=root->val;
if(root->left==NULL&&root->right==NULL){
if(sum==targetSum) result.push_back(path);
}
if(root->left) func(root->left,path,sum,targetSum);
if(root->right) func(root->right,path,sum,targetSum);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if(root==NULL) return{};
vector<int> path;
func(root,path,0,targetSum);
return result;
}
};
106.从中序与后序遍历序列构造二叉树
题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
文章链接:https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size()==0) return NULL;
//找到后序的最后一个元素,为根节点,进行分割
int rootNum=postorder[postorder.size()-1];
TreeNode* root=new TreeNode(rootNum);
//叶节点
if(postorder.size()==1) return root;
//根据前序来分割,找到左右子树
int index=0;
for(index;index<inorder.size();index++){
if(inorder[index]==rootNum) break;
}
vector<int> leftInorder(inorder.begin(),inorder.begin()+index);
vector<int> rightInorder(inorder.begin()+index+1,inorder.end());
//根据前序左右子树的大小,分割后序序列
vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end()-1);
//构造左子树
root->left=buildTree(leftInorder,leftPostorder);
root->right=buildTree(rightInorder,rightPostorder);
return root;
}
};
标签:right,return,int,找树,sum,随想录,左下角,root,left
From: https://www.cnblogs.com/VickyWu/p/18535983