温州建设银行官方网站,宿迁市工厂外包工加工,多少钱网站设计,兰州优化网站公司513.找树左下角的值 本题用前中后序都可以#xff08;都是先遍历左再遍历右#xff0c;保证最后一定是左侧的节点#xff09;#xff0c;因为没有中节点的处理逻辑#xff0c;用全局变量记录最大深度#xff0c;只要遇到叶子结点并且当前深度比最大深度大#xff0c;就更… 513.找树左下角的值 本题用前中后序都可以都是先遍历左再遍历右保证最后一定是左侧的节点因为没有中节点的处理逻辑用全局变量记录最大深度只要遇到叶子结点并且当前深度比最大深度大就更新同时用到了回溯。 深度最大的叶子结点是最后一行。左侧的节点不一定是左孩子。 class Solution {
public:int maxDepth0;int res;void traversal(TreeNode* node,int depth){if(node-leftNULL!node-rightdepthmaxDepth){maxDepthdepth;resnode-val;}if(node-left){depth;traversal(node-left,depth);depth--;}if(node-right){depth;traversal(node-right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {traversal(root,1);return res;}
}; 迭代法层序遍历 用每一层的第一个元素更新结果值res最后返回的就是最后一层第一个元素。每次循环队列都要一边弹出元素一边加入元素。 class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;if(root) que.push(root);int res;while(!que.empty()){//先记录当前层的元素个数int sizeque.size();for(int i0;isize;i){TreeNode* nodeque.front();que.pop();if(i0) resnode-val;if(node-left) que.push(node-left);if(node-right) que.push(node-right);}}return res;}
}; 112. 路径总和 也是前中后序都可以不存在中节点的处理逻辑。代码中有两处返回false的逻辑第一处是单条路径不符合的话返回false第二处是如果所有的路径尝试后都没有返回true的话就返回false。注意传入下层递归函数的值是已经减去节点后的值。 class Solution {
public:bool traversal(TreeNode* node,int curSum){if(!node-left!node-rightcurSum0) return true;else if(!node-left!node-rightcurSum!0) return false;//以上两个返回信息仅用于递归时if(node-left){curSum-node-left-val;if(traversal(node-left,curSum)) return true;//下面的孩子节点告诉当前节点存在路径那就继续向上返回true的信息curSumnode-left-val;}if(node-right){curSum-node-right-val;if(traversal(node-right,curSum)) return true;curSumnode-right-val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return traversal(root,targetSum-root-val);}
}; 113.路径总和ii 注意终止条件有两个符合/不符合然后注意在进行下一层递归之前path已经记录了节点的数值传入递归函数的数也是减去后的数。 class Solution {
public:vectorvectorint res;vectorint path;void traversal(TreeNode* node,int cursum){//终止条件有两个一个是符合条件一个是不符合条件if(!node-left!node-rightcursum0){res.push_back(path);return;}if(!node-left!node-right) return;if(node-left){path.push_back(node-left-val);cursum-node-left-val;traversal(node-left,cursum);cursumnode-left-val;path.pop_back();}if(node-right){path.push_back(node-right-val);cursum-node-right-val;traversal(node-right,cursum);cursumnode-right-val;path.pop_back();}}vectorvectorint pathSum(TreeNode* root, int targetSum) {res.clear();path.clear();if(!root) return res;path.push_back(root-val);traversal(root,targetSum-root-val);return res;}
}; 106.从中序与后序遍历序列构造二叉树 1、如果后序数组的元素个数为0则返回NULL 2、如果不为空取后序数组最后一个元素为根节点的值 3、找到后序数组最后一个元素在中序数组中的位置 4、切中序数组 5、切后序数组 6、递归构造二叉树 class Solution {
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {if(postorder.size()0) return NULL;//如果不为空取后序数组最后一个元素为节点元素int rootvalpostorder[postorder.size()-1];TreeNode* rootnew TreeNode(rootval);if(postorder.size()1) return root;//找后序数组最后一个元素在中序数组中的位置作为切割点int idx;for(idx0;idxinorder.size();idx){if(inorder[idx]rootval) break;}//切中序数组vectorint leftinorder(inorder.begin(),inorder.begin()idx);vectorint rightinorder(inorder.begin()idx1,inorder.end());//切后序数组postorder.resize(postorder.size()-1);vectorint leftpostorder(postorder.begin(),postorder.begin()leftinorder.size());vectorint rightpostorder(postorder.begin()leftinorder.size(),postorder.end());root-leftbuildTree(leftinorder,leftpostorder);root-rightbuildTree(rightinorder,rightpostorder);return root;}
}; 105.从前序与中序遍历序列构造二叉树 class Solution {
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.size()0) return NULL;int rootvalpreorder[0];TreeNode* rootnew TreeNode(rootval);if(preorder.size()1) return root;int index;for(index0;indexinorder.size();index){if(inorder[index]preorder[0]) break;}vectorint leftinorder(inorder.begin(),inorder.begin()index);vectorint rightinorder(inorder.begin()index1,inorder.end());vectorint leftpreorder(preorder.begin()1,preorder.begin()leftinorder.size()1);vectorint rightpreorder(preorder.begin()leftinorder.size()1,preorder.end());root-leftbuildTree(leftpreorder,leftinorder);root-rightbuildTree(rightpreorder,rightinorder);return root;}
}; 划分左中序区间的时候边界问题出错。
