二叉树的问题的解决思维
1.[遍历]. 思考是否通过遍历一遍二叉树得到答案, 如果可以, 用一个 traverse 函数配合外部变量实现: 在遍历的思维下, 其实是在二叉树上进行 dfs 的操作, dfs 的时候该回溯时要回溯操作, 用某个关键变量记录递归到某个节点时候的 [某种状况]
2.[问题的可分解性], 简称为 [分解]. 思考当前 [原问题], 是否有与 [原问题] 相同的 [子问题], 如果 [原问题] 和 [子问题] 是一类问题, 我们就可以思考 [原问题] 和 [子问题] 之间的关系是什么, 思考清楚了[原问题] 和 [子问题] 之间的关系是什么, 其实递归函数也就定义清楚了. 如何思考 [原问题] ? 假设只有一个根节点和两个左右孩子且叶子节点, 应该是个怎样的问题
3.无论使用那种思维模式, 单独抽出来二叉树, 我们要做的是思考它需要做什么事情, 需要在什么时候 (前/中/后序位置) 做?
深入理解前中后序遍历的区别
1.遍历二叉树和遍历数组或者链表并无本质区别
// 迭代遍历数组
void traverse(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
// visit i
}
}
// 递归遍历数组
void traverse(vector<int>&arr, int i) {
if (i == arr.size()) {
return;
}
// 前序位置, 刚进入节点的时候
traverse(arr, i + 1);
// 后序位置, 即将离开节点的时候
}
// 迭代遍历链表
void traverse(ListNode* head) {
for (ListNode* p = head; p != nullptr; p = p->next) {
}
}
// 递归遍历链表
void traverse(ListNode* head) {
if (head == nullptr) {
return;
}
// 前序位置, 刚进入节点的时候
traverse(head->next);
// 后序位置, 即将离开节点的时候
}
一个典型例子的是倒序打印一条单链表上的所有节点, 利用[后序位置]来操作
void traverse(ListNode* head) {
if (head == nullptr) {
return;
}
traverse(head->next);
// 后序位置
print(head->val);
}
2.前序/中序/后序遍历二叉树的本质区别
三者的区别在于 [处理当前节点的时间点] 不同
[前序位置] 的逻辑处理在刚刚进入一个二叉树节点的时候执行
[后序位置] 的逻辑处理在将要离开一个二叉树节点的时候执行
[中序位置] 的逻辑处理在一个二叉树左子树都遍历完, 即将开始遍历右子树的时候执行
二叉树的所有问题, 就是让在前中后序 [位置] 对应加入某些代码逻辑, 去达到目的, 只需要思考每个节点应该做什么
前序位置的代码执行是自顶向下的, 后序位置的代码执行是自底向上的
leetcode 中定义二叉树的结构如下
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) {}
};
遍历 v.s. 原问题和子问题之间的同质性
104.二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
分析:
1.遍历思维求解, curDepth 当前遍历到节点的深度
class Solution {
private:
int res = 0;
int curDepth = 0; // 维护当前的深度
public:
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
++depth;
// 如果到了叶子节点, 尝试更新最大深度
if (root->left == nullptr && root->right == nullptr) {
res = max(res, depth);
}
// 遍历左孩子
traverse(root->left);
// 遍历右孩子
traverse(root->right);
// 回溯
--depth;
return;
}
int maxDepth(TreeNode* root) {
traverse(root);
return res;
}
};
2.若采用 [分解] 问题的思维
(i).对于任意一个根节点来说, 我们想看看当前根节点的最大深度和 (两个) 子节点的最大深度之间的关系是什么, 对于它的左孩子来说, 计算左子树的最大深度和计算原根节点的最大深度是同一个问题, 因此可以考虑递归的想法
(ii).根节点的最大深度, 之和他的左右子树的最大深度有关, 具体来说这个关系可以写成
根节点的最大深度 = max(它的左子树最大深度, 它的右子树的最大深度) + 1(根节点自己带来的深度)
(iii).从操作的[位置]来看, 其实对应的是上面后序位置进行一个累加操作
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftMaxDepth = maxDepth(root->left);
int rightMaxDepth = maxDepth(root->right);
return max(leftMaxDepth, rightMaxDepth) + 1;
}
};
669.修建二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。示例 1：输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]
示例 2：输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]
分析:
1.递归地处理不合理的位置的解决问题
2.如果当前节点是 nullptr, 直接返回
3.如果当前节点
5.如果当前节点位于[low, high], 将他的左子树和右子树递归修建
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
return root;
}
if (root->val < low) {
return trimBST(root->right, low, high);
}
if (root->val > high) {
return trimBST(root->left, low, high);
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
后序位置的特殊之处
1.刚才提到前序和后续有一个区别, 前序遍历是自上而下的, 后序遍历是自下而上的
2.前序位置逻辑处理只能从获取父节点传递过来数据, 而后序位置还可以获取到子树通过函数返回值传递回来的数据
3.通过以下两个问题体会后序遍历的特殊之处
4.如果把根节点当做第1层, 打印出每一个节点所在的层
5.如何打印出每个节点的左右子树各有多少节点
// 4.如果把根节点当做第1层, 打印出每一个节点所在的层
void traverse(TreeNode* root, int level) {
if (root == nullptr) {
return;
}
cout << "节点" << root->val << " 在" << level << " 层";
traverse(root->left, level + 1);
traverse(root->right, level + 1);
}
traverse(root, 1);
// 5.如何打印出每个节点的左右子树各有多少节点
void countSonNodes(TreeNode* root) {
if (root == nullptr) {
return;
}
int leftCnt = countSonNodes(root->left);
int rightCnt = countSonNodes(root->right);
cout << "节点" << root->val << " 左子树有" << leftCnt << " 右子树有" << rightCnt;
return leftCnt + rightCnt + 1;
}
因此, 如果发现题目和子树有关, 那么大概率要在在后序位置处理一些逻辑
543.二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例: 给定二叉树
1 / \ 2 3 / \ 4 5返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
分析:
1.具体到一个根节点, 它所在的直径等于最大深度等于什么?
2.如果能想到对于一个根节点, 它的直径等于 [左子树数的最大深度] 和 [右子树的最大深度] 之和
3.我们写一个最大深度的函数, 然后不断更新这个最大深度
4.一个二叉树的的最大深度是怎么来的 ? 是另一个可以用分解的思维去思考的问题, 对于一个根节点来说, 它的最大深度等于 max(左子树的最大深度, 右子树的最大深度) + 1
class Solution {
private:
int ans = 0;
public:
// 写一个求最大深度的函数
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int lMaxDepth = maxDepth(root->left);
int rMaxDepth = maxDepth(root->right);
// 对于一个根节点而言, 它的直径等于 [左子树数的最大深度] 和 [右子树的最大深度] 之和;
int diameter = lMaxDepth + rMaxDepth;
ans = max(ans, diameter);
// 对于一个根节点而言, 最大深度等于 max(lMaxDepth, rMaxDepth) + 1;
return max(lMaxDepth, rMaxDepth) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
maxDepth(root);
return ans;
}
};
124.二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。示例 1：输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
-10
/ \
9 20
/ \ / \
-2 15 7
分析:
1.因为最大路径和可以不包含根节点, 所以我们要遍历出来以每个根节点为根节点的二叉树的最大路径和, 然后迭代出来最大的, 所以我们分析下以某个根节点为根节点的二叉树的最大路径和怎么来的?
2.以当前根节点为根节点的二叉树的最大路径和 = 根节点的值 + 左子树的最大路径和 + 右子树的最大路径和; 左子树的最大路径和是什么 ? 这里每个节点是有正有负的, 如果左子树最大路径和是个负数, 那么我们把左子树的负增益要砍掉, 反而是最大的; 所以准确地说, 我们考虑的左子树的最大路径和, 考虑的是经过左孩子为根节点的向下路径求和增益 (右子树同理); 以当前根节点为根节点的二叉树的最大路径和 = 根节点的值 + 经过左孩子为根节点的向下路径求和增益 + 经过右孩子为根节点的向下路径求和增益, 其中, 增益表示的是至少是个 >= 0 的值
经过左孩子为根节点的向下路径求和增益 = max(viaRootPathSumGain(root->left), 0)
经过左孩子为根节点的向下路径求和增益 = max(viaRootPathSumGain(root->right), 0)
3.所以, 我们要写的函数是 viaRootPathSumGain(), 代表了经过 root 为根节点的向下路径的求和增益, 这个路径上的增益是什么? 根节点的值加左右增益路径中最大的一边的值: 经过 root 为根节点的向下路径的下求和增益 = root->val + max(经过左孩子为根节点的向下路径求和增益, 经过右孩子为根节点的向下路径求和增益)
class Solution {
private:
int ans = INT_MIN;
public:
// viaRootPathSumGain 返回经过 root 为根节点的向下路径的求和增益
int viaRootPathSumGain(TreeNode* root) {
if (root == nullptr) {
return 0;
}
// 经过左/右孩子节点的向下陆景求和增益, 增益表示限制下界是0, 路径和为负数一律不考虑
int lPathSumGain = max(viaRootPathSumGain(root->left), 0);
int rPathSumGain = max(viaRootPathSumGain(root->right), 0);
// 后序位置迭代: 求经过 root 的二叉树的最大路径和
// 经过 root 的二叉树的最大路径和 = root 的值 + 经过左孩子为根节点的向下路径求和增益 + 经过右孩子为根节点的向下路径求和增益
int curPathSum = root->val + lPathSumGain + rPathSumGain;
ans = max(ans, curPathSum);
// 经过 root 为根节点的向下路径的求和增益 = root->val + max(经过左孩子为根节点的向下路径求和增益, 经过右孩子为根节点的向下路径求和增益)
return root->val + max(lPathSumGain, rPathSumGain);
}
int maxPathSum(TreeNode* root) {
viaRootPathSumGain(root);
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
