513. 找树左下角的值
下面运用层序遍历法比较简单,当遍历到一层时设立一个值去不断覆盖一层的队头,即最左边元素
class Solution { public: int findBottomLeftValue(TreeNode* root) { int leftnum; queue<TreeNode*>qe; if(root!=NULL)qe.push(root); while(!qe.empty()){ int size=qe.size(); leftnum=qe.front()->val; for(int i=0;i<size;i++){ if(qe.front()->left)qe.push(qe.front()->left); if(qe.front()->right)qe.push(qe.front()->right); qe.pop(); } } return leftnum; } };
下面是运用前序遍历递归法,寻找最大深度过程中不断覆盖结果值,优先考虑左边,当深度相同时保证最底层右边值不会覆盖结果值。
class Solution { public: int result; int maxDepth=INT_MIN; void traversal(TreeNode* root,int depth){ if(root->left==NULL&&root->right==NULL){ if(depth>maxDepth){ maxDepth=depth; result=root->val; } } if(root->left){ depth++; traversal(root->left,depth); depth--; } if(root->right){ depth++; traversal(root->right,depth); depth--; } } int findBottomLeftValue(TreeNode* root) { traversal(root,1); return result; } };
112. 路径总和
下面运用层序遍历法,遍历每一层并重新改变val数据域,再加一个判断,判断是否为叶子节点并val值是否为目标值。
class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { queue<TreeNode*>qe; if(root!=NULL)qe.push(root); while(!qe.empty()){ int size=qe.size(); for(int i=0;i<size;i++){ if(qe.front()->left)qe.front()->left->val+=qe.front()->val,qe.push(qe.front()->left); if(qe.front()->right)qe.front()->right->val+=qe.front()->val,qe.push(qe.front()->right); if(!qe.front()->right&&!qe.front()->left&&qe.front()->val==targetSum)return 1; qe.pop(); } } return 0; } };
下面是运用递归回溯法
class Solution { public: bool travesal(TreeNode* root,int count){ if(root->right==NULL&&root->left==NULL&&count==0)return 1; if(root->left==NULL&&root->right==NULL)return 0; if(root->left){ count-=root->left->val; if(travesal(root->left,count))return 1; count+=root->left->val; } if(root->right){ count-=root->right->val; if(travesal(root->right,count))return 1; count+=root->right->val; } return 0; } bool hasPathSum(TreeNode* root, int targetSum) { if(root==NULL)return 0; return travesal(root,targetSum-root->val); return 0; } };
113. 路径总和 II
这题和上面那题改了一下,递归函数不能有返回值,因为是遍历整个树所有路径。
class Solution { public: vector<vector<int>>result; vector<int>path; void traversal(TreeNode* root,int count){ if(root->right==NULL&&root->left==NULL&&count==0){ result.push_back(path); return; } if(root->left==NULL&&root->right==NULL)return; if(root->left){ count-=root->left->val; path.push_back(root->left->val); traversal(root->left,count); count+=root->left->val; path.pop_back(); } if(root->right){ count-=root->right->val; path.push_back(root->right->val); traversal(root->right,count); count+=root->right->val; path.pop_back(); } } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if(root==NULL)return {}; path.push_back(root->val); traversal(root,targetSum-root->val); return result; } };
106. 从中序与后序遍历序列构造二叉树
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 delimiterIndex; for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 切割中序数组 // 左闭右开区间:[0, delimiterIndex) vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); // [delimiterIndex + 1, end) vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); // postorder 舍弃末尾元素 postorder.resize(postorder.size() - 1); // 切割后序数组 // 依然左闭右开,注意这里使用了左中序数组大小作为切割点 // [0, leftInorder.size) vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); // [leftInorder.size(), end) 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); } };
标签:right,return,val,后序,106,qe,二叉树,root,left From: https://www.cnblogs.com/zhishikele/p/17054339.html