代码随想录day16

513.找树左下角的值

//迭代法中左视图的最后一位

int findBottomLeftValue(TreeNode* root) { int result = 0; queue<TreeNode*> qe; if(root == nullptr) return result; qe.push(root); vector<int> lefts; while(!qe.empty()){ int sz = qe.size(); vector<int> tmp; for(int i = 0; i < sz; i++){ TreeNode* nd = qe.front(); qe.pop(); tmp.push_back(nd->val); if(nd->left) qe.push(nd->left); if(nd->right) qe.push(nd->right); } lefts.push_back(tmp[0]); } result = lefts[lefts.size()-1]; return result; }

//递归法，保证左侧优先遍历，注意回溯

int maxDepth = INT_MIN; int result; void traverse(TreeNode*node, int depth){ if(node->left == nullptr && node->right == nullptr){ if(depth > maxDepth){ maxDepth = depth; result = node->val; } return; } if(node->left){ traverse(node->left, depth+1); } if(node->right){ traverse(node->right, depth+1); } return; }

111.路径总和

bool traverse(TreeNode* node, int target){ if(node->left == nullptr && node->right == nullptr){ if(target == node->val){ return true; }else{ return false; } } if(node->left){ if(traverse(node->left, target - node->val)){ return true; } } if(node->right){ if(traverse(node->right, target - node->val)){ return true; } } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(root == nullptr) return false; return traverse(root, targetSum); }

113.路径之和ii

vector<vector<int>> result; vector<int> path; void traverse(TreeNode* node, int target){ if(node->left == nullptr && node->right == nullptr){ if(target == node->val){ path.push_back(node->val); result.push_back(path); path.pop_back(); } return; } if(node->left){ path.push_back(node->val); traverse(node->left, target - node->val); path.pop_back(); } if(node->right){ path.push_back(node->val); traverse(node->right, target - node->val); path.pop_back(); } return; } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if(root == nullptr) return result; traverse(root, targetSum); return result; }

106.从中序与后序遍历序列构造二叉树，需二刷

需记住中序，后序分割后的左右子串数量一致

TreeNode* traverse(vector<int>& inorder, vector<int>& postorder){ if(inorder.size() == 0 || postorder.size() == 0){ return nullptr; } int rootval = postorder[postorder.size()-1]; TreeNode* root = new TreeNode(rootval); if(postorder.size() == 1){ return root; } int dim = 0; for(int i = 0; i < inorder.size(); i++){ if(inorder[i] == rootval){ dim = i; } } vector<int> leftinorder(inorder.begin(), inorder.begin()+dim); vector<int> rightinorder(inorder.begin()+dim+1, inorder.end()); postorder.resize(postorder.size()-1); vector<int> leftpostorder(postorder.begin(), postorder.begin()+leftinorder.size()); vector<int> rightpostorder(postorder.begin()+leftinorder.size(), postorder.end()); root->left = traverse(leftinorder, leftpostorder); root->right = traverse(rightinorder, rightpostorder); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(inorder.size() == 0 || postorder.size() == 0){ return nullptr; } return traverse(inorder, postorder); }

105.从前序与中序遍历序列构造二叉树

TreeNode* traverse(vector<int>& preorder, vector<int>& inorder){ if(preorder.size() == 0 || inorder.size() == 0){ return nullptr; } int rootval = preorder[0]; TreeNode* root = new TreeNode(rootval); if(preorder.size() == 1){ return root; } int dim = 0; for(;dim < inorder.size(); dim++){ if(inorder[dim] == rootval){ break; } } vector<int> leftinorder(inorder.begin(), inorder.begin()+dim); vector<int> rightinorder(inorder.begin()+dim+1, inorder.end()); preorder.erase(preorder.begin()); vector<int> leftpreorder(preorder.begin(),preorder.begin()+leftinorder.size()); vector<int> rightpreorder(preorder.begin()+leftinorder.size(),preorder.end()); root->left = traverse(leftpreorder, leftinorder); root->right = traverse(rightpreorder, rightinorder); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size() == 0 || inorder.size() == 0){ return nullptr; } return traverse(preorder, inorder); }