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
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
vector
traversal(root, targetSum, {}, ans);
return ans;
}
106.从中序与后序遍历序列构造二叉树
这题的重点是理解如何递归地分割序列
中间节点（当前节点）是后序序列的最后一个元素
· 中序序列分割：以中间节点为界进行分割，前面的是左子树的中序序列，后面的是右子树的中序序列
· 后序序列分割：后序序列分割后的长度与中序序列分割后的长度统一，根据长度依次分割出左右子树的后序序列
注意需要先分割中序再分割后序，因为分割后序序列需要中序序列的长度信息
需要先获取当前节点才能分割出左右子树，所以使用前序遍历：
递归——前序遍历
思路：将当前序列不断分割出当前节点、左子树序列、右子树序列，递归地构造二叉树
· 返回值类型：TreeNode*，返回当前节点所代表子树的指针
· 传入参数：
vector
vector
· 单层递归逻辑——前序遍历：
中：先获取节点值（等于后序序列的最后一个元素）并创建当前节点，根据当前节点分割左右子树的中序和后序序列。
左：递归地获取左子树，将其地址赋给当前节点的左子树
右：递归地获取右子树，将其地址赋给当前节点的右子树
TreeNode* traversal(vector
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
vector
// 分割后序序列
auto iterPost = postorder.begin() + leftIn.size(); // 利用长度与中序序列相同的特性
vector
vector
// 左
cur->left = traversal(leftIn, leftPost);
// 右
cur->right = traversal(rightIn, rightPost);
return cur;
}
TreeNode* buildTree(vector
return traversal(inorder, postorder);
}
105. 从前序与中序遍历序列构造二叉树
与上一题一样，仅有分割方法稍有不同，这次中间节点值为前序序列的第一个元素。
TreeNode* traversal(vector
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
vector
// 分割前序序列
auto iterPre = preorder.begin() + leftIn.size() + 1; // 利用长度与中序序列相同的特性
vector
vector
// 左
cur->left = traversal(leftPre, leftIn);
// 右
cur->right = traversal(rightPre, rightIn);
return cur;
}
TreeNode* buildTree(vector
return traversal(preorder, inorder);
}
推荐链接
发表评论