广平企业做网站推广,建设网站的策划书,公众号做电影网站,游戏类网站欣赏513.找树左下角的值
leetcode题目地址 题目链接/文章讲解/视频讲解
如果使用递归法#xff0c;如何判断是最后一行#xff1a; 其实就是深度最大的叶子节点一定是最后一行。
//迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNod…513.找树左下角的值
leetcode题目地址 题目链接/文章讲解/视频讲解
如果使用递归法如何判断是最后一行 其实就是深度最大的叶子节点一定是最后一行。
//迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);int result 0;while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (i 0) result node-val; // 记录最后一行第一个元素if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result;}
};//递归法
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) {traversal(root-left, depth 1); // 隐藏着回溯下一个遍历的时候深度加一本层的不变}if (root-right) {traversal(root-right, depth 1); // 隐藏着回溯, 下一个遍历的时候深度加一本层的不变}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};
112. 路径总和
leetcodet题目链接 题目链接/文章讲解/视频讲解 因为终止条件是判断叶子节点所以递归的过程中就不要让空节点进入递归了。 递归函数是有返回值的如果递归函数返回true说明找到了合适的路径应该立刻返回。 左右子树递归时候的返回值要做判断如果有一支返回true就可以提前返回结果如果都没有返回true返回false
class Solution {
private:bool traversal(TreeNode* cur, int count) {if (!cur-left !cur-right count 0) return true; // 遇到叶子节点并且计数为0if (!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 sum) {if (root NULL) return false;return traversal(root, sum - root-val);}
};106.从中序与后序遍历序列构造二叉树
106.从中序与后序遍历序列构造二叉树105.从前序与中序遍历序列构造二叉树 leetcode题目链接 题目链接/文章讲解/视频讲解 说到一层一层切割就应该想到了递归。 来看一下一共分几步 第一步如果数组大小为零的话说明是空节点了。 第二步如果不为空那么取后序数组最后一个元素作为节点元素。 第三步找到后序数组最后一个元素在中序数组的位置作为切割点 第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组 第五步切割后序数组切成后序左数组和后序右数组 第六步递归处理左区间和右区间
//框架代码
TreeNode* traversal (vectorint inorder, vectorint 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;}// 第四步切割中序数组得到 中序左数组和中序右数组// 第五步切割后序数组得到 后序左数组和后序右数组// 第六步root-left traversal(中序左数组, 后序左数组);root-right traversal(中序右数组, 后序右数组);return root;
}//完整代码
class Solution {
private:TreeNode* traversal (vectorint inorder, vectorint 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)vectorint leftInorder(inorder.begin(), inorder.begin() delimiterIndex);// [delimiterIndex 1, end)vectorint rightInorder(inorder.begin() delimiterIndex 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size());// [leftInorder.size(), end)vectorint rightPostorder(postorder.begin() leftInorder.size(), postorder.end());root-left traversal(leftInorder, leftPostorder);root-right traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;return traversal(inorder, postorder);}
};
