我局 负责 建设 网站,全国最新产品代理,罗湖网站建设哪家好,网页传奇新游开服目录
513.找树左下角的值
前言
层序遍历
递归法
112. 路径总和
前言 递归法
113. 路径总和ii
前言
递归法
106.从中序与后序遍历序列构造二叉树
前言
思路
递归法
总结 513.找树左下角的值 题目链接 文章链接 前言 本题要求得到二叉树最后一行最左边的值#xf…目录
513.找树左下角的值
前言
层序遍历
递归法
112. 路径总和
前言 递归法
113. 路径总和ii
前言
递归法
106.从中序与后序遍历序列构造二叉树
前言
思路
递归法
总结 513.找树左下角的值 题目链接 文章链接 前言 本题要求得到二叉树最后一行最左边的值使用层序遍历可以较为容易地实现使用递归法要再次用到回溯对不满足条件的路径进行回退。
层序遍历
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;int result 0;if (root NULL) return result;que.push(root);vector int vec;while (!que.empty()){int size que.size();vec {}; //每层遍历都要初始化vec数组for (int i 0; i size; i){TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result vec[0];}
}; 因为最终只要获得最后一行的节点数值所以vec容器每层都要重新初始化进行收集直到最后一层此时容器中保存的即为最后一行的节点数值第一个就是符合条件的左下角的值。
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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. 路径总和 题目链接 文章链接 前言 本题的目的在于更好地理解递归函数什么时候要有返回值什么时候没有返回值。 在确定递归函数的参数和返回类型时参数需要二叉树的根节点还需要一个计数器这个计数器用来计算二叉树的一条边之和是否正好是目标和计数器为int型。 递归函数什么时候需要返回值什么时候不需要返回值这里总结如下三点
如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值。 如果需要搜索整棵二叉树且需要处理递归返回值递归函数就需要返回值。如果要搜索其中一条符合条件的路径那么递归一定需要返回值因为遇到符合条件的路径了就要及时返回。 递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public: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;}bool hasPathSum(TreeNode* root, int targetSum) {if (root NULL) return false;return traversal(root, targetSum - root-val);}
}; 掌握本题后下面一题就好理解了。
113. 路径总和ii 题目链接 文章链接 前言 路径总和ii要遍历整个树找到所有路径所以递归函数不要返回值
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:vectorvectorint result;vectorint path;void traversal(TreeNode* cur, int count){if (!cur-left !cur-right count 0){result.push_back(path);return;}if (!cur-left !cur-right) return;if (cur-left){path.push_back(cur-left-val); count - cur-left-val;traversal(cur-left, count);count cur-left-val;path.pop_back();}if (cur-right){path.push_back(cur-right-val);count - cur-right-val;traversal(cur-right, count);count cur-right-val;path.pop_back();}return;}public:vectorvectorint pathSum(TreeNode* root, int targetSum) {if (root NULL) return result;path.push_back(root-val);traversal(root, targetSum - root-val);return result;}
};
106.从中序与后序遍历序列构造二叉树 题目链接 文章链接 前言 本题要根据两个遍历顺序构造一个唯一的二叉树整体思路是以后序数组的最后一个元素为切割点先切中序数组根据中序数组反过来再切后序数组。一层一层切下去每次后序数组最后一个元素就是节点元素。
思路
实现步骤 第一步判断数组大小是否为零为零说明是空节点了 第二步如果不为零那么取后序数组最后一个元素作为根节点元素 第三步找到后序数组最后一个元素在中序数组的位置作为切割点 第四步切割中序数组切成中序左数组和中序右数组 第五步切割后序数组切成后序左数组和后序右数组 第六步递归处理左区间和右区间
递归法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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 index;for (index 0; index inorder.size(); index){if (inorder[index] rootValue) break;} //第四步 切割中序数组 得到 中序左数组和中序右数组//左闭右开区间vectorint leftInorder(inorder.begin(), inorder.begin() index);vectorint rightInorder(inorder.begin() index 1, inorder.end());//第五步 切割后序数组 得到 后序左数组和后序右数组postorder.resize(postorder.size() - 1);vectorintleftPostorder(postorder.begin(), postorder.begin() leftInorder.size());vectorintrightPostorder(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) return NULL;return traversal(inorder, postorder);}
}; 要注意切割时边界值的判断。
总结 重点掌握巩固二叉树的递归实现以及二叉树递归参数及返回值的确定。
