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 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
class Solution {
private:
bool ans = false;
public:
void dfs(TreeNode* root, int targetSum, int sum) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr && sum + root->val == targetSum) {
ans = true;
return;
}
dfs(root->left, targetSum, sum + root->val);
dfs(root->right, targetSum, sum + root->val);
return;
}
bool hasPathSum(TreeNode* root, int targetSum) {
dfs(root, targetSum, 0);
return ans;
}
};
257.二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
示例 1：输入：root = [1,2,3,null,5] 输出：[“1->2->5”,”1->3”]
示例 2：输入：root = [1] 输出：[“1”]
分析:
1.直接 dfs
class Solution {
private:
vector<string> ans;
public:
void dfs(TreeNode* root, string s) {
if (root == nullptr) {
return;
}
s += to_string(root->val);
if (root->left == nullptr && root->right == nullptr) {
ans.push_back(s);
} else {
s += "->";
dfs(root->left, s);
dfs(root->right, s);
}
return;
}
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "");
return ans;
}
};
129.求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。示例 1：输入：root = [1,2,3] 输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25示例 2：输入：root = [4,9,0,5,1] 输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
分析:
1.dfs 遍历求和
class Solution {
private:
int ans = 0;
public:
void dfs(TreeNode* root, int cur) {
if (root == nullptr) {
return;
}
int data = cur * 10 + root->val;
if (root->left == nullptr && root->right == nullptr) {
ans += data;
}
dfs(root->left, data);
dfs(root->right, data);
return;
}
int sumNumbers(TreeNode* root) {
dfs(root, 0);
return ans;
}
};
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
分析:
1.回溯搜索
class Solution {
private:
vector<vector<int>> ans;
public:
void dfs(vector<int>& path, TreeNode* root, int targetSum, int accSum) {
if (root == nullptr) {
return;
}
path.emplace_back(root->val);
int curSum = accSum + root->val;
if (root->left == nullptr && root->right == nullptr && curSum == targetSum) {
ans.emplace_back(path);
}
dfs(path, root->left, targetSum, curSum);
dfs(path, root->right, targetSum, curSum);
path.pop_back();
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return ans;
}
vector<int> path;
dfs(path, root, targetSum, 0);
return ans;
}
};
437.路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。示例 1：输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：310 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
分析:
1.这个题中提到的路径不需要从根节点开始, 而是累计以根节点为根节点包含下的所有 (经过或者不经过根节点) 的路径. 因此用分解问题的思维, 以根节点为根节点的所有路径总和, 等于左子树包含的路径总和 + 右子树包含的路径总和 + 以根节点为必经节点下的路径总和; 写成代码就是 pathSum(root->left) + pathSum(root->right) + rootViaSum(root), 其中 rootViaSum(root) 以根节点为必经节点下的路径总和
2.所以我们思考如何计算 rootViaSum(root) , 也就是以某个具体的根节点为根节点, 然后必须经过这个根节点的路径总和; 这里又要采用另一个分解思维: 当前的这个求和为 targetSum 的话, 可以有 3 种方式, 一种是一开始根节点就能满足路径总和, 另外两种是根节点和下面左子树凑出来路径总和, 以及根节点和右子树凑出来路径总和
class Solution {
public:
// rootViaSum 计算必须经过这个根节点的路径总和
int rootViaSum(TreeNode* root, long long targetSum) {
if (root == nullptr) {
return 0;
}
// 计算必须经过这个根节点的路径总和 = 可能的根节点值等于 target的情况=1/否则0 + 根节点和下面左子树凑出来路径总和 + 根节点和下面右子树凑出来的路径总和
return ((root->val == targetSum) ? 1 : 0) + rootViaSum(root->left, targetSum - root->val) + rootViaSum(root->right, targetSum - root->val);
}
int pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return 0;
}
// 以根节点为根节点的所有路径总和 = 左子树包含的路径总和 + 右子树包含的路径总和 + 以根节点为必经节点下的路径总和
return rootViaSum(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
};
666.路径总和 IV
对于一棵深度小于 5 的树，可以用一组三位十进制整数来表示。对于每个整数：
百位上的数字表示这个节点的深度 d，1 <= d <= 4。
十位上的数字表示这个节点在当前层所在的位置 P， 1 <= p <= 8。位置编号与一棵满二叉树的位置编号相同。
个位上的数字表示这个节点的权值 v，0 <= v <= 9。
给定一个包含三位整数的 升序 数组 nums ，表示一棵深度小于 5 的二叉树，请你返回 从根到所有叶子结点的路径之和 。
保证 给定的数组表示一个有效的连接二叉树。示例 1：输入: nums = [113, 215, 221] 输出: 12
解释: 列表所表示的树如上所示。
路径和 = (3 + 5) + (3 + 1) = 12.示例 2：输入: nums = [113, 221] 输出: 4 解释: 列表所表示的树如上所示。 路径和 = (3 + 1) = 4.
分析:
1.这道题一个朴素的思路是还原树然后再dfs, 这样比较复杂
2.能不能直接进行一种dfs, 且不还原树?
3.这里每个节点可以通过深度+位置唯一标识根节点的位置, root = 10 depth + pos, 正好是前2位, root = num / 10, 那么它的左孩子怎么标识?
4.左孩子 = 10 (depth + 1) + 2 * pos - 1, 右孩子 = 左孩子 + 1
5.可以把所有的结构放在一个map里面进行遍历
class Solution {
private:
int ans = 0;
unordered_map<int, int> nodeHash;
public:
void dfs(int key, int curSum) {
if (nodeHash.find(key) == nodeHash.end()) {
return;
}
curSum += nodeHash[key];
int depth = key / 10;
int pos = key % 10;
int left = 10 * (depth + 1) + 2 * pos - 1;
int right = left + 1;
if (nodeHash.find(left) == nodeHash.end() && nodeHash.find(right) == nodeHash.end()) {
ans += curSum;
}
dfs(left, curSum);
dfs(right, curSum);
return;
}
int pathSum(vector<int>& nums) {
for (auto& e : nums) {
nodeHash[e / 10] = e % 10;
}
dfs(nums[0] / 10, 0);
return ans;
}
};
250.统计同值子树
给定一个二叉树，统计该二叉树数值相同的子树个数。
同值子树是指该子树的所有节点都拥有相同的数值。示例：输入: root = [5,1,5,5,5,null,5], 输出: 4
5
/ \
1 5
/ \ \
5 5 5
分析:
1.理解题意, 什么叫做同值子树, 对一个根节点来说
(i). 如果它的左右子树都为 nullptr, 那么算一个同值子树
(ii). 如果它的所有子节点的值都相同, 那么算一个同值子树
2.对于每个根节点来说, 需要判定一棵树所有节点都相同, 然后在这个过程中去计数同值子树的个数; 这里有一层逻辑的过渡是在于, 我如果能判断一棵树的所有节点都相同=>我就能统计同值子树的个数, 其实这个判断就是分析第1点
3.判定一棵树所有节点所有节点都相同, 等价于判定左孩子所有节点都相同, 且右孩子所有节点都相同, 且值等于当前根节点
class Solution {
private:
int ans = 0;
public:
// dfs判定一棵树所有节点都相同(节点为空也算相同)
bool judgeAllSameDFS(TreeNode* root, int value) {
if (root == nullptr) {
return true;
}
bool lSonAllSame = judgeAllSameDFS(root->left, root->val);
bool rSonAllSame = judgeAllSameDFS(root->right, root->val);
if (lSonAllSame && rSonAllSame) {
++ans;
if (value == root->val) {
return true;
}
}
return false;
}
int countUnivalSubtrees(TreeNode* root) {
if (root == nullptr) {
return 0;
}
judgeAllSameDFS(root, root->val);
return ans;
}
};
687.最长同值路径
给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。示例 1: 输入：root = [5,4,5,1,1,5] 输出：2
示例 2: 输入：root = [1,4,5,4,4,5] 输出：2
分析:
1.dfs算的是以root为节点当前搜索的同值最长路径的长度, 同时在递归的时候动态更新最长同值的路径
class Solution {
private:
int ans = 0;
public:
int longestUnivaluePathDFS(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int lSonLUP = longestUnivaluePathDFS(root->left);
int rSonLUP = longestUnivaluePathDFS(root->right);
int leftLUP = 0;
int rightLUP = 0;
if (root->left != nullptr && root->left->val == root->val) {
leftLUP = lSonLUP + 1;
}
if (root->right != nullptr && root->right->val == root->val) {
rightLUP = rSonLUP + 1;
}
ans = max(ans, leftLUP + rightLUP);
return max(leftLUP, rightLUP);
}
int longestUnivaluePath(TreeNode* root) {
longestUnivaluePathDFS(root);
return ans;
}
};
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 = [] 输出：[]
分析:
1.尝试用两种思维解决这个问题
2.遍历思维, 从上往下翻转
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* intermediary = root->left;
root->left = root->right;
root->right = intermediary;
invertTree(root->left);
invertTree(root->right);
return root;
}
};
3.分解思维, 先拿到翻转的结果, 然后自下而上翻转
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* l = invertTree(root->left);
TreeNode* r = invertTree(root->right);
root->left = r;
root->right = l;
return root;
}
};
转载请注明来源, from goldandrabbit.github.io
