代码随想录算法训练营Day18 | 513. 找树左下角的值、112.路径总和、106.从中序与后序遍历序列构造二叉树
513.找树左下角的值
这题按照之前的前序遍历思路也不算难,但是为了判断条件需要建很多变量,细节也很多。
递归——前序遍历
思路:保存最大深度与最大左转次数。满足以下条件之一则进行更新:
1、当前层数大于最大层数
2、当前层数等于最大层数,但左转次数大于最大左转次数
· 返回值类型:void,不需要返回值,将结果使用一个引用进行维护即可
· 传入参数:
TreeNode* cur:当前节点的指针
int depth:当前深度
int& maxDepth:最大深度
int leftTurn:当前左转次数
int& maxLeft:最大左转次数
int &ans:当前左下角的值
· 单层递归逻辑——前序遍历:
中:如果当前节点是叶子节点则检测是否满足更新条件,如果满足则更新结果
左:递归访问左孩子,深度+1,左转次数+1
右:递归访问右孩子,深度+1,左转次数不变
void traversal(TreeNode* cur, int depth, int leftTurn, int& maxDepth, int& maxLeft, int& ans) { if (!cur) return; if (!cur->left && !cur->right) { // 更新条件:层数更大,或层数相同但左转次数更多 if ((depth > maxDepth) || (depth == maxDepth && leftTurn > maxLeft)) { ans = cur->val; } // 这里直接可以返回,但要在更新结果时也对maxDepth和maxLeft进行更新 } maxDepth = std::max(depth, maxDepth); maxLeft = std::max(leftTurn, maxLeft); traversal(cur->left, depth + 1, leftTurn + 1, maxDepth, maxLeft, ans); traversal(cur->right, depth + 1, leftTurn, maxDepth, maxLeft, ans); } int findBottomLeftValue(TreeNode* root) { int ans = root->val; int maxDepth = 1; int maxLeft = 0; traversal(root, 1, 0, maxDepth, maxLeft, ans); return ans; }
迭代法非常简单:使用层序遍历,记录每层第一个遍历到的节点则是当前的左下角节点。
112.路径总和
依旧使用前序遍历
递归——前序遍历
思路:不断记录当前路径总和,当到达叶子节点时判断是否等于目标
· 返回值类型:void,不需要返回值,将结果使用一个引用进行维护即可
· 传入参数:
TreeNode* cur:当前节点的指针
int sum:当前路径总和
int& targetSum:目标路径和(可以优化掉,使sum初始值==targetSum)
bool &ans:判断是否有符合题目要求路径的布尔值,初始为false
· 单层递归逻辑——前序遍历:
中:先更新路径总和,如果当前节点是叶子节点则检测路径总和是否等于目标值,如果等于则将ans更新为true
左:递归访问左孩子
右:递归访问右孩子
void traversal(TreeNode* cur, int sum, int& targetSum, bool& ans) { // 节点为空时返回,找到目标值时也直接返回 if (ans || !cur) return; sum += cur->val; // 和等于目标值且为叶节点时,将结果设置为true if (sum == targetSum && !cur->left && !cur->right) { ans = true; return; } traversal(cur->left, sum, targetSum, ans); traversal(cur->right, sum, targetSum, ans); } bool hasPathSum(TreeNode* root, int targetSum) { bool ans = false; if (root) traversal(root, 0, targetSum, ans); return ans; }
113.路径总和II
与上题一样,不同的仅有将ans从布尔值变为一个记录结果的vector数组
void traversal(TreeNode* cur, int sum, vector path, vector& ans) { if (!cur) return; // 中 sum -= cur->val; // 更新路径 path.push_back(cur->val); if (!sum && !cur->left && !cur->right) { // 符合条件则将当前路径加入结果数组 ans.push_back(path); return; } //左 traversal(cur->left, sum, path, ans); // 右 traversal(cur->right, sum, path, ans); } vector pathSum(TreeNode* root, int targetSum) { vector ans; traversal(root, targetSum, {}, ans); return ans; }
106.从中序与后序遍历序列构造二叉树
这题的重点是理解如何递归地分割序列
中间节点(当前节点)是后序序列的最后一个元素
· 中序序列分割:以中间节点为界进行分割,前面的是左子树的中序序列,后面的是右子树的中序序列
· 后序序列分割:后序序列分割后的长度与中序序列分割后的长度统一,根据长度依次分割出左右子树的后序序列
注意需要先分割中序再分割后序,因为分割后序序列需要中序序列的长度信息
需要先获取当前节点才能分割出左右子树,所以使用前序遍历:
递归——前序遍历
思路:将当前序列不断分割出当前节点、左子树序列、右子树序列,递归地构造二叉树
· 返回值类型:TreeNode*,返回当前节点所代表子树的指针
· 传入参数:
vector inorder:当前子树的中序序列
vector postorder:当前子树的后序序列
· 单层递归逻辑——前序遍历:
中:先获取节点值(等于后序序列的最后一个元素)并创建当前节点,根据当前节点分割左右子树的中序和后序序列。
左:递归地获取左子树,将其地址赋给当前节点的左子树
右:递归地获取右子树,将其地址赋给当前节点的右子树
TreeNode* traversal(vector inorder, vector postorder){ if (inorder.empty()) return nullptr; // 中 int val = *(postorder.end() - 1); TreeNode* cur = new TreeNode(val); // 这里得创建在堆区,不然节点会被自动销毁 // 如果是叶子节点,直接进行返回(剪枝) if (inorder.size() == 1) return cur; // 分割中序序列 auto iterIn = std::find(inorder.begin(), inorder.end(), val); // 以根节点为界 vector leftIn(inorder.begin(), iterIn); vector rightIn(iterIn + 1, inorder.end()); // 分割后序序列 auto iterPost = postorder.begin() + leftIn.size(); // 利用长度与中序序列相同的特性 vector leftPost(postorder.begin(), iterPost); vector rightPost(iterPost, postorder.end() - 1); // 左 cur->left = traversal(leftIn, leftPost); // 右 cur->right = traversal(rightIn, rightPost); return cur; } TreeNode* buildTree(vector& inorder, vector& postorder) { return traversal(inorder, postorder); }
105. 从前序与中序遍历序列构造二叉树
与上一题一样,仅有分割方法稍有不同,这次中间节点值为前序序列的第一个元素。
TreeNode* traversal(vector preorder, vector inorder) { if (preorder.empty()) return nullptr; // 中 int val = preorder[0]; TreeNode* cur = new TreeNode(val); // 这里得创建在堆区,不然会自动销毁 // 如果是叶子节点,直接进行返回(剪枝) if (inorder.size() == 1) return cur; // 分割中序序列 auto iterIn = std::find(inorder.begin(), inorder.end(), val); // 以根节点为界 vector leftIn(inorder.begin(), iterIn); vector rightIn(iterIn + 1, inorder.end()); // 分割前序序列 auto iterPre = preorder.begin() + leftIn.size() + 1; // 利用长度与中序序列相同的特性 vector leftPre(preorder.begin() + 1, iterPre); vector rightPre(iterPre, preorder.end()); // 左 cur->left = traversal(leftPre, leftIn); // 右 cur->right = traversal(rightPre, rightIn); return cur; } TreeNode* buildTree(vector& preorder, vector& inorder) { return traversal(preorder, inorder); }
还没有评论,来说两句吧...