二叉树专题训练二
5/2
T700 二叉搜索树中的搜索
【复习定义】 二叉搜索树是一个有序树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树
这题虽然很简单，但可以学一下写法：
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) return root;
if (val < root->val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
};
加粗这行将null、匹配这两种情况一并处理，让下面的分支直接调用方法即可，和T617的优化写法异曲同工。总之，注意代码优雅性，优雅的本质是简洁以让bug发生率低。
T617 合并二叉树
这一题也是递归，想清楚后不难，注意不同null个数传入值的处理方式即可。当心：不可直接将null传入值补充成新的值为0的节点，因为遇到两个null就会出现错误；GPT优化后，发现一个null的情况也不需要新建0节点，直接将非null传入值作为子树返回链接即可。
//新建root=v1+v2
//对于传入值均非null：
//获取左子树的返回值（传入root1.left,root2.left）作为新root左子节点
//获取右子树的返回值（传入root1.right,root2.right作为新root右子节点
//对于有一个传入值为null：直接返回非空传入值对应的节点作为子节点
//对于两个传入值皆为null的：不做任何处理（不调用方法，不做链接）（注意这里不必返回，因为没有方法调用）
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr && root2 == nullptr) return nullptr;
int v1 = root1 ? root1->val : 0;
int v2 = root2 ? root2->val : 0;
TreeNode* root = new TreeNode(v1 + v2);
//左子树
TreeNode* l1 = root1 ? root1->left : nullptr;
TreeNode* l2 = root2 ? root2->left : nullptr;
if (l1 != nullptr && l2 != nullptr) {
root->left = mergeTrees(l1, l2);
} else if (l1 != nullptr) {
root->left = l1;
} else if (l2 != nullptr) {
root->left = l2;
} else {
}
//右子树（同理
TreeNode* r1 = root1 ? root1->right : nullptr;
TreeNode* r2 = root2 ? root2->right : nullptr;
if (r1 != nullptr && r2 != nullptr) {
root->right = mergeTrees(r1, r2);
} else if (r1 != nullptr) {
root->right = r1;
} else if (r2 != nullptr) {
root->right = r2;
} else {
}
return root;
}
};
【有趣的事】根据逻辑推理，
if (root1 == nullptr && root2 == nullptr) return nullptr;
int v1 = root1 ? root1->val : 0;
int v2 = root2 ? root2->val : 0;
TreeNode* root = new TreeNode(v1 + v2);
这几行代码当且仅当在第一轮循环中出现，也就是测试数据出现空树的情况，在后面的代码里是无可能出现的。验证代码：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// ===== 只在这里处理 null =====
if (root1 == nullptr) return root2;
if (root2 == nullptr) return root1;
// 保证下面传入的都是非空
return merge(root1, root2);
}
private:
TreeNode* merge(TreeNode* root1, TreeNode* root2) {
// ❗这里默认 root1 和 root2 一定非空
TreeNode* root = new TreeNode(root1->val + root2->val);
// 左子树
TreeNode* l1 = root1->left;
TreeNode* l2 = root2->left;
if (l1 && l2) {
root->left = merge(l1, l2);
} else if (l1) {
root->left = l1;
} else if (l2) {
root->left = l2;
}
// 右子树
TreeNode* r1 = root1->right;
TreeNode* r2 = root2->right;
if (r1 && r2) {
root->right = merge(r1, r2);
} else if (r1) {
root->right = r1;
} else if (r2) {
root->right = r2;
}
return root;
}
};
【优化】以上代码看起来很长，不优雅，原因是我们分情况处理了子节点null的情况，这是不必要的。将空节点统一放在开头的处理已经允许我们直接传入null指针，因为左右子树针对null的处理逻辑本质和开头一样，是复用。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// 两个都为空
if (root1 == nullptr && root2 == nullptr) return nullptr;
// 只有一个不为空：直接返回
if (root1 == nullptr) return root2;
if (root2 == nullptr) return root1;
// 都不为空：新建节点 = 相加
TreeNode* root = new TreeNode(root1->val + root2->val);
// 递归构造左右子树
root->left = mergeTrees(root1->left, root2->left);
root->right = mergeTrees(root1->right, root2->right);
return root;
}
};
5/1
T654 最大二叉树
题干已将算法思路点出，和下面两题无本质区别。注意空数组的处理方式（加粗代码）。
class Solution {
private:
// 在左闭右开区间[left, right)，构造二叉树
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left >= right) return nullptr;
// 分割点下标：maxValueIndex
int maxValueIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
}
TreeNode* root = new TreeNode(nums[maxValueIndex]);
// 左闭右开：[left, maxValueIndex)
root->left = traversal(nums, left, maxValueIndex);
// 左闭右开：[maxValueIndex + 1, right)
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
#
【重要】前序和后序不能唯一确定一棵二叉树 例如：tree1 的前序遍历是[1 2 3]， 后序遍历是[3 2 1] 这棵树既可以往左侧一路延伸下去，也可以往右侧延伸下去
T105 从前序与中序遍历序列构造二叉树
和T106思路完全一致，代码略。
T06 从中序与后序遍历序列构造二叉树
这道题经典之极，今天把变种也一起梳理清楚。关键有两点，其一是后序遍历最后一个值属于新root节点，可以利用来切割中序数组；其二是中序数组对应的“左”“右”和后序数组对应的“左”“右”虽顺序不同，但集合相同，每组节点个数相同——中序左右可以分别切割后序左右，如此轮回。递归的方式也很直接，每次新建数组即可。
【优化】利用四个指针代替新建数组，直接在原数组上处理
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};
4/30
T112 路径总和
该题重点在于优化。基础思路很好想，显然是个可以通过递归求解的题目：
//如果根节点为null，根据示例，返回false
//创建返回值为int数组的新方法，输入值为node
//递归
//分别取左、右非空节点的返回值数组，对每个值加上当前节点的值
//取元素互异的并集作为新返回数组（下面代码未去重，不影响结果）
//遍历新方法的返回数组，有匹配值则true，无则false
代码如下：
class Solution {
public:
// 返回从当前节点到所有叶子节点的路径和集合
vector<int> getSums(TreeNode* node) {
vector<int> res;
if (node == nullptr) return res;
// 叶子节点
if (node->left == nullptr && node->right == nullptr) {
res.push_back(node->val);
return res;
}
// 左子树
if (node->left) {
vector<int> leftSums = getSums(node->left);
for (int x : leftSums) {
res.push_back(x + node->val);
}
}
// 右子树
if (node->right) {
vector<int> rightSums = getSums(node->right);
for (int x : rightSums) {
res.push_back(x + node->val);
}
}
return res;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return false;
vector<int> sums = getSums(root);
for (int x : sums) {
if (x == targetSum) return true;
}
return false;
}
};
这样做需要对所有路径求和，时间复杂度高，对本题是没必要的。许多测试样子中，只要找到一条这样的叶根路径即可，不必遍历所有。 【最优解】
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return false;
// 到叶子节点
if (root->left == nullptr && root->right == nullptr) {
return targetSum == root->val;
}
// 递归左右子树（边走边减）
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}
};
【关键】 1、取或是很重要的优化，尤其在递归中，可以大幅降低复杂度
2、非必要无需自创新方法，从这一题可以发现，leetcode原题自带的方法函数有期巧妙性，例如这里的 int targetSum 显然就是期望我们每次调用时传入新值减去当前节点的值
3、随遍历逐渐减去某值的做法很常见，这种渐变的思路一定当心不要使用同一静态全局变量，每次需传入独立的值
T513 找树左下角的值
不知道这道题为何被归为中等难度，我觉得很简单。直接层序遍历+设置一个tmp即可：
//层序遍历，每次记录当前层所有孩子的个数以得知什么时候来到了下一层
//用tmp指针指向第一个出来的当前层节点也就是当前层最左侧
//检验是否该层的孩子个数（也就是下一层节点数）为零， 若是，返回tmp指针节点的值
实际上，第三行注释是不必要的，因为在层序遍历的queue里最后一个for循环必定将最底层节点推出：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int result = root->val; // 初始化
while (!q.empty()) {
int size = q.size(); // 当前层节点数
// 当前层第一个节点就是最左节点
result = q.front()->val;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
};
这一题唯一值得关注的点是：不必上来就往递归思路想，二叉树刷多了会有惯性思维。这道题明显和“层”的概念强相关，层序遍历本身又自然而然适应寻找最左侧节点这一概念，因此思路直截了当。
刷完二叉树专题后，理应归纳出一套方法论，秒杀经典题目。【待完成】
4/29
T404 左叶子之和
1、关键要判断叶子节点是否为左，这需要传入父节点带来的信息，故新开一个方法
//新建一个包含多一个int的方法，其他相同，int初始值为0
//遍历左节点时，传入int=1，右节点则传入int=2
//假如root为空，返回0
//获取非空左、右节点的返回值
//返回两者之和
//若都为空且自己是左叶子节点，返回自己的值；否则返回零
//将新方法root的返回值作为题干方法的返回值
对应代码：
class Solution {
public:
int dfs(TreeNode* node, int flag) {
if (!node) return 0;
// 叶子节点
if (!node->left && !node->right) {
if (flag == 1) return node->val; // 是左叶子
return 0;
}
int left = dfs(node->left, 1);
int right = dfs(node->right, 2);
return left + right;
}
int sumOfLeftLeaves(TreeNode* root) {
return dfs(root, 0);
}
};
2、如果我不想创建新方法，有一个优化写法——既然无法得知自己是否为左叶子节点，就不管自己，直接探查自己的左节点是否为左叶子节点，类似提前判断，在具备较多信息时便出手判断。两个方法的核心都是一致的：找出左叶子节点，该节点自己的值需计入sum。只是方法一将关注点聚焦于自己是否为左叶子，方法二聚焦为左孩子是否为左叶子。
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
int sum = 0;
// 判断左孩子是不是叶子
if (root->left && !root->left->left && !root->left->right) {
sum += root->left->val;
}
// 继续递归
sum += sumOfLeftLeaves(root->left);
sum += sumOfLeftLeaves(root->right);
return sum;
}
};
【备忘】练习一下手写数组转树、树转数组、存储方式微迁移的代码，并测试
T257 二叉树的所有路径
1、发现了很适合构造递归思路的方法：直接照着示例在脑中模拟代码运行，想想看每一步要返回什么值，如何处理这些值
2、明确每次用到的数组或其他存储结构是全局静态还是每个递归循环中新建的
3、所有返回值和题干函数保持一致，尤其空节点的情况；以及，示例中的题目输入存在可视化便利化，真实输入以题干代码框架为基准
4、if (!root) return res;不要忘记，处理特殊情况
5、记住该函数的语法：
for (string s : right) {
res.push_back(to_string(root->val) + "->" + s);
}
本题思路：
//初始化
//递归
//对于非空左节点的返回值，把所有字符串的前缀加上当前节点的序号，对非空右节点也如此；返回左右节点合并后的数组；假如左右节点返回值都为空，则返回当前节点的序号对应的数组；
本题代码：
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
// 空节点
if (!root) return res;
// 递归获取左右子树路径
vector<string> left = binaryTreePaths(root->left);
vector<string> right = binaryTreePaths(root->right);
// 如果左右子树都为空，说明是叶子节点
if (left.empty() && right.empty()) {
res.push_back(to_string(root->val));
return res;
}
// 处理左子树
for (string s : left) {
res.push_back(to_string(root->val) + "->" + s);
}
// 处理右子树
for (string s : right) {
res.push_back(to_string(root->val) + "->" + s);
}
return res;
}
};
【二次复习时可探索：回溯算法】
4/27
T110 平衡二叉树
1、这道题我忽略一个关键点：每次判断当前节点下的左右子树是否平衡时，还应判断左、右子树分别作为整体时是否平衡嘛，即加粗放大的两行代码：
class Solution {
public:
int getHeight(TreeNode* node) {
if (node == nullptr) return 0;
int left = getHeight(node->left);
if (left == -1) return -1; // 左子树不平衡
int right = getHeight(node->right);
if (right == -1) return -1; // 右子树不平衡
if (abs(left - right) > 1) return -1; // 当前不平衡
return max(left, right) + 1; // 返回高度
}
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
};
2、注意高度的定义，最后一步计算时不是直接取左右子树的高度最大值，要加一
3、由于需要返回高度，整个递归的返回值都是数值类型，我们就不能直接返回false，而应该用数字（例如-1）替代判断
4、谨慎处理空节点，这里空节点并不代码false，故返回0即可
T222 完全二叉树的节点个数
1、这一题我第一反应用层序遍历计数，是对的，且让我发现层序遍历实际上并不需要每回统计一层总数，直接pop到队列为空即可：
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> q;
q.push(root);
int count = 0;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
count++;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return count;
}
};
2、但这并非最优解。最优解很有趣，有一个前置推断：假设左子树非满二叉树，则右子树必定比左子树高度少一层。所以，如果左子树高度 = 右子树高度，左子树必然是满二叉树。 由此可用类似二分法的思想递归下去，核心： 情况 1：左高 == 右高 说明： 左子树是满二叉树 节点数 = 左子树节点数 + 当前节点 + 右子树节点数 = (2^h - 1) + 1 + 递归右子树 = 2^h + count(right)
情况 2：左高 != 右高 说明： 右子树是满二叉树（少一层） 节点数 = = count(left) + 2^h
class Solution {
public:
int getHeight(TreeNode* node) {
int h = 0;
while (node) {
h++;
node = node->left;
}
return h;
}
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (leftHeight == rightHeight) {
// 左子树是满二叉树
return (1 << leftHeight) + countNodes(root->right);
} else {
// 右子树是满二叉树
return (1 << rightHeight) + countNodes(root->left);
}
}
};