代码随想录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);}