代码随想录算法训练营第18天

标签：return cur E5% 18 训练营 随想录 traversal root postorder

今日刷题5道：513.找树左下角的值，112. 路径总和 ，113.路径总和ii，106.从中序与后序遍历序列构造二叉树 ，105.从前序与中序遍历序列构造二叉树

●  513.找树左下角的值

题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

 

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){             depth++;             traversal(root->left, depth);             depth--;  //回溯，返回上一层         }         if(root -> right){             depth++;             traversal(root->right, depth);             depth--;         }         return;     }     int findBottomLeftValue(TreeNode* root) {         traversal(root, 0);         return result;     } };

●  112. 路径总和 113.路径总和ii

题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

 

class Solution { private:     bool traversal(TreeNode* cur, int count){         if(!cur->left && ! cur->right && count==0) return true;         if(!cur->left && !cur->right) return false;         if(cur->left){             count -= cur->left->val;             if(traversal(cur->left, count)) return true;             count += cur->left->val;         }         if(cur->right){             count -= cur->right->val;             if(traversal(cur->right, count)) return true;             count += cur->right->val;         }         return false;     } public:     bool hasPathSum(TreeNode* root, int targetSum) {         if(root == NULL) return false;         return traversal(root,targetSum - root->val);     } };

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

题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

 

class Solution { private:     TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){         if(postorder.size()==0) return NULL;         int rootValue = postorder[postorder.size()-1];         TreeNode* root = new TreeNode(rootValue);         if(postorder.size()==1) return root;         int delineterIndex;         for(delineterIndex=0;delineterIndex<inorder.size();delineterIndex++){             if(inorder[delineterIndex] == rootValue) break;         }         vector<int> leftInorder(inorder.begin(),inorder.begin()+delineterIndex);         vector<int> rightInorder(inorder.begin()+delineterIndex+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 = traversal(leftInorder,leftPostorder);         root->right = traversal(rightInorder,rightPostorder);         return root;


    } public:     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {         if(inorder.size()==0 || postorder.size()==0) return NULL;         return traversal(inorder,postorder);     } };

标签：return,cur,E5%,18,训练营,随想录,traversal,root,postorder
From： https://www.cnblogs.com/zzw0612/p/17051601.html