目录
二叉树某一节点X祖先节点的交集（证明题）
LeetCode_100. 相同的树
LeetCode_965. 单值二叉树
LeetCode_101. 对称二叉树
LeetCode_226. 翻转二叉树
LeetCode_112. 路径总和
LeetCode_113. 路径总和 II
LeetCode_110. 平衡二叉树
LeetCode_98. 验证二叉搜索树
二叉树中最大的二叉搜索子树的大小
LeetCode_105. 从前序与中序遍历序列构造二叉树
总结
二叉树某一节点X祖先节点的交集（证明题）
题目描述：
对于某个二叉树，X是二叉树中某一个节点，得到了整棵树的先序遍历，也知道这颗树的后序遍历。
则有结论：先序遍历X之前的节点定义为集合A，后序遍历X之后的节点定义为集合B,，则 A∩B得到的集合就是X的祖先节点集合
思路分析：
二叉树的前序遍历的顺序为：当前节点->左子树->右子树，而后续遍历的顺序为：左子树->右子树->当前节点。所以对于某个节点X，其所有的祖先节点一定在先序序列的前面，一定在后续序列的后面。所以A∩B得到的集合就是X的祖先节点集合
LeetCode_100. 相同的树
题目描述：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题思路很简单，就是两棵树从根开始对比，如果根节点相等，就接着判断左子树是否相等，然后接着判断右子树是否相等。
仔细看，这里的思路就是前序遍历的思路，都是先处理当前节点，然后左子树，右子树。
我的题解：
/**
* 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 isSameTree(TreeNode* p, TreeNode* q)
{
//base case
if(p == nullptr && q == nullptr)
return true;
else if(p == nullptr || q == nullptr)
return false;
//normal case
if(p->val == q->val)
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
return false;
}
};LeetCode_965. 单值二叉树
题目描述：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1]
输出：true
示例 2：
输入：[2,2,2,5,2]
输出：false
提示：
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/univalued-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
由于条件是绝对的所有节点的数值相等，所以就以根节点为基准进行判断。按照左子树，右子树的顺序判断。需要注意控制空节点的边界条件。
我的题解：
/**
* 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 isUnivalTree(TreeNode* root)
{
if(root == nullptr)
return true;
int val = root->val;
//左右子树为空的情况就直接默认符合条件
int left = root->left == nullptr ? val : root->left->val;
int right = root->right == nullptr ? val : root->right->val;
if(left == val && right == val)
return isUnivalTree(root->left) && isUnivalTree(root->right);
return false;
}
};LeetCode_101. 对称二叉树
题目描述：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
由于是判断对称，所以直接不用管根节点，先判断左右子树是否相等，然后进一步判断左子树的右子树是否等于右子树的左子树，并且右子树的右子树是否等于左子树的左子树。
上述过程大致也可以分成是前序遍历，先判断根的左右节点树是否是对称的，然后判断左子树是否对称，接着判断右子树去是否对称。先操作根节点，然后左子树，右子树。
/**
* 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 judge(TreeNode* l, TreeNode* r)
{
//base case
if(l == nullptr && r == nullptr)
return true;
else if(l == nullptr || r == nullptr)
return false;
//normal case
if(l->val == r->val)
return judge(l->left, r->right) && judge(l->right, r->left);
return false;
}
bool isSymmetric(TreeNode* root)
{
return judge(root->left, root->right);
}
};LeetCode_226. 翻转二叉树
题目描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题和对称二叉树有些相似之处，大体思路就是将左右子树交换。这里我们从叶子节点开始，将两个同一父母的叶子节点交换，从下往上。
这就是后续遍历的做法（这题用前序遍历也能做）
我的题解：
/**
* 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:
TreeNode* invertTree(TreeNode* root)
{
/*先反转左右子树，再反转当前节点*/
//base case
if(root == nullptr)
return nullptr;
//normal case
invertTree(root->left);
invertTree(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = right;
root->right = left;
return root;
}
};LeetCode_112. 路径总和
题目描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题的一个核心思路就是：设置一个sum用于保存当前路径的和，当走到叶子节点且符合条件时就返回true，当走完整棵树的时候就说明没有符合条件的路径和，返回false。
注意：只有走到根节点的时候才能判断要返回true，还是继续，还是退出。即使某一个中间分支节点的路径和已经符合条件了也不行，必须是叶子节点才可以。
我的题解：
/**
* 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 _hasPathSum(TreeNode* root, int curSum, int targetSum)
{
//base case
curSum += root->val;
if(root->left == nullptr && root->right == nullptr)
return curSum == targetSum;
//noremal case
bool left = false, right = false;
if(root->left != nullptr)
left = _hasPathSum(root->left, curSum, targetSum);
if(root->right != nullptr)
right = _hasPathSum(root->right, curSum, targetSum);
return left || right;
}
bool hasPathSum(TreeNode* root, int targetSum)
{
//base case
if(root == nullptr)
return false;
//normal case
return _hasPathSum(root, 0, targetSum);
}
};LeetCode_113. 路径总和 II
题目描述：
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：输入：root = [1,2], targetSum = 0
输出：[]
提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题其实就是在上一题的基础上改版。我们只需要针对性的修改即可。
但值得注意的是，对于path数组何时push_back进来，何时pop_back出去的问题我们需要拿捏好才行。需要形成一个闭环才走得通，要不然不是越界错误，就是结果错误。
我的题解：
/**
* 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:
public:
void pathSumCreate(TreeNode* root,vector<int>& curPath, int curSum, int targetSum, vector<vector<int>>& Path)
{
//base case
curPath.push_back(root->val);
curSum += root->val;
if(root->left == nullptr && root->right == nullptr && curSum == targetSum)
{
Path.push_back(curPath);
curSum -= root->val;
}
if(root->left != nullptr)
{
pathSumCreate(root->left, curPath, curSum, targetSum, Path);
curPath.pop_back();
}
if(root->right != nullptr)
{
pathSumCreate(root->right, curPath, curSum, targetSum, Path);
curPath.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
vector<vector<int>> Path;
vector<int> curPath;
if(root == nullptr)
return Path;
pathSumCreate(root, curPath, 0, targetSum, Path);
return Path;
}
};LeetCode_110. 平衡二叉树
题目描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
一个很常规的思路就是获得两个子树的高度，判断是否合法，接着走到两个子树的位置，再判断。但这样有一个很大的开销就是获取子树的高度。
所以我们可以把获取树的高度的代码稍加修改，将判断平衡的过程融入进去。
这里我们就发现：如果一个题目需要用到一些信息，那么我们可以尝试着写一个获取信息的代码，然后将题目的具体要求融入到这个代码中，进而达到一个高效的目的。但这只适用于像这题这种只需要一个或者很少信息的情况。
我的题解：
/**
* 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 subHight(TreeNode* root)
{
//base case
if(root == nullptr)
return true;
//
int left = subHight(root->left);
int right = subHight(root->right);
if(left == -1 || right == -1 || abs(left - right) > 1)
return -1;
return max(left, right) + 1; //返回高度
}
bool isBalanced(TreeNode* root)
{
return subHight(root) > 0;
}
};LeetCode_98. 验证二叉搜索树
题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题我们介绍两种做法。
做法1：中序遍历
就是保证左边最大小于当前节点，右边最小大于当前节点，并且左右子树都是二叉查找树。细节看代码：
/** * 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: long long preVal = LLONG_MIN; //初始化为最小值 public: bool isValidBST(TreeNode* root) { //base case if(root == nullptr) return true; //中序遍历 /*左*/ if(!isValidBST(root->left)) return false; /*中*/ if(root->val <= preVal) return false; preVal = root->val; /*右*/ return isValidBST(root->right); } };做法2：树型DP
树型DP这里要介绍一下，树型DP的通用模板就是：根据题目的要求分析出所需要的信息info，然后通过一个process过程对树进行操作，最终头节点的info就是我们想要的。
比如这题，我们是通过左边最大小于当前节点，右边最小大于当前节点，并且左右子树都是二叉查找树来判断的，所以我们分析出所需要的信息就是以当前节点为根的最大值，最小值，和是否为二叉查找树。接下来我们就是利用这些信息解决问题了。
代码实现如下：
/** * 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 isValidBST(TreeNode* root) { return process(root)->isBST; } struct info { bool isBST; int max; int min; info (bool _is, int _max, int _min) : isBST(_is), max(_max), min(_min) {} }; info* process(TreeNode* root) { if(root == nullptr) return nullptr; info* left = process(root->left); info* right = process(root->right); bool is = true; int cur_max = root->val, cur_min = root->val; if(left != nullptr) { cur_max = std::max(cur_max, left->max); cur_min = std::min(cur_min, left->min); is = is && left->isBST && root->val > left->max; } if(right != nullptr) { cur_max = std::max(cur_max, right->max); cur_min = std::min(cur_min, right->min); is = is && right->isBST && root->val < right->min; } return new info(is, cur_max, cur_min); } };
二叉树中最大的二叉搜索子树的大小
题目描述：
链接：找到二叉树中的最大搜索二叉子树__牛客网
来源：牛客网
给定一颗二叉树，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，输出该子树总节点的数量。
搜索二叉树是指对于二叉树的任何一个节点，都大于其左子树中的全部节点，但是小于其右子树中的全部节点。
输入描述:
第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。 以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理) ps:节点的编号就是节点的值。
注意：子树必须包含其所有后代。
题目分析：
这题还是使用树型DP的方法比较好做。先分析，想要知道最大二叉查找树的大小，可以分为两种情况：最大二叉查找树包括根节点的情况，最大二叉查找树不包括根节点的情况。而这两种情况的判断就需要左右子树是否是二叉查找树，左右子树节点的个数，左右子树最大二叉查找树的节点个数，左右子树的最大、最小值这5个信息，我们发现如果最大二叉查找树的节点个数恰好等于节点个数的话，那么此时这颗子树就是二叉查找树，所以我们设置info的时候就可以少维护一个信息，只需要写4个信息即可。
具体的代码实现如下：
#include <iostream>
using namespace std;
struct node
{
int val;
node* left;
node* right;
node() :val(0), left(nullptr), right(nullptr) {}
node(int _val) :val(_val), left(nullptr), right(nullptr) {}
};
class solution
{
private:
node* buyTree()
{
int val, l_val, r_val;
cin >> val >> l_val >> r_val;
node* root = new node(val);
if (l_val) root->left = buyTree();
if (r_val) root->right = buyTree();
return root;
}
struct info
{
int max;
int min;
int maxBSTsize;
int nodeSize;
info(int _max, int _min, int _maxBST, int _nodeSize) :
max(_max), min(_min), maxBSTsize(_maxBST), nodeSize(_nodeSize) {}
};
info* process(node* root)
{
if (root == nullptr)
return nullptr;
info* left = process(root->left);
info* right = process(root->right);
int cur_max = root->val, cur_min = root->val, node_size = 1;
int p1 = -1, p2 = -1, p3 = -1;
bool is_left = true, is_right = true;
if (left != nullptr)
{
cur_max = std::max(cur_max, left->max);
cur_min = std::min(cur_min, left->min);
node_size += left->nodeSize;
p1 = left->maxBSTsize;
is_left = left->maxBSTsize == left->nodeSize && root->val > left->max;
}
if (right != nullptr)
{
cur_max = std::max(cur_max, right->max);
cur_min = std::min(cur_min, right->min);
node_size += right->nodeSize;
p2 = right->maxBSTsize;
is_right = right->maxBSTsize == right->nodeSize && root->val < right->min;
}
if (is_left && is_right)
p3 = (!left ? 0 : left->nodeSize) + (!right ? 0 : right->nodeSize) + 1;
int maxBST = std::max(std::max(p1, p2), p3);
return new info(cur_max, cur_min, maxBST, node_size);
}
public:
int getMaxBSTsize()
{
//创建树
int n, val;
cin >> n >> val; //用不到
node* tree = buyTree();
return process(tree)->maxBSTsize;
}
};
int main()
{
cout << solution().getMaxBSTsize() << endl;
return 0;
}
LeetCode_105. 从前序与中序遍历序列构造二叉树
题目描述：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路分析：
这题就是模拟，没什么特别的。
我的题解：
/**
* 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:
unordered_map<int,int> indexMap; //key - index
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
int size = preorder.size();
TreeNode* newTree = nullptr;
for(int i = 0; i < size; i++)
{
indexMap[inorder[i]] = i;
}
return _buildTree(preorder, 0, size - 1, inorder, 0, size - 1);
}
private:
TreeNode* _buildTree(vector<int>& preorder, int pre_left, int pre_right, vector<int>& inorder, int in_left, int in_right)
{
if(pre_right < pre_left || in_right < in_left)
return nullptr;
TreeNode* newNode = new TreeNode(preorder[pre_left]);
/*这里写的太乱了，要改一下*/
int in_root = indexMap[preorder[pre_left]];
int left_num = in_root - in_left, right_num = in_right - in_root;
newNode->left = _buildTree(preorder, pre_left + 1, pre_left + left_num, inorder, in_left, in_root - 1);
newNode->right = _buildTree(preorder, pre_right - right_num + 1, pre_right, inorder, in_root + 1, in_right);
return newNode;
}
}; 总结
做二叉树的题常规思路就是：前序、中序、后续遍历，层序遍历，树型DP与模拟
