【数据结构与算法 | 灵神题单 | 自底向上DFS篇】力扣965, 2331, 100, 1379
1. 力扣965：单值二叉树
1.1 题目：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1] 输出：true
示例 2：
输入：[2,2,2,5,2] 输出：false
提示：
- 给定树的节点数范围是
[1, 100]。 - 每个节点的值都是整数，范围为
[0, 99]。
1.2 思路：
dfs，有点类似于斐波那契数列，知道下面的值，才能算出来上面的值。这题也一样，一直递归，从下往上返回。
1.3 题解：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int dig;
public boolean isUnivalTree(TreeNode root) {
// 因为树中节点数是至少有一个的，所以直接把root的val复制给dig全局变量
dig = root.val;
return dfs(root);
}
private boolean dfs(TreeNode node) {
// 如果node为null时，遍历完，直接返回true
if(node == null){
return true;
}
// 判断这个节点的值是不是等于dig，以及
// 它的左子树的情况和右子树的情况
return (node.val == dig) && dfs(node.left) && dfs(node.right);
}
}2. 力扣2331：计算布尔二叉树的值
2.1 题目：
给你一棵 完整二叉树 的根，这棵树有以下特征：
- 叶子节点 要么值为
0要么值为1，其中0表示False，1表示True。 - 非叶子节点 要么值为
2要么值为3，其中2表示逻辑或OR，3表示逻辑与AND。
计算 一个节点的值方式如下：
- 如果节点是个叶子节点，那么节点的 值 为它本身，即
True或者False。 - 否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
示例 1：
输入：root = [2,1,3,null,null,0,1] 输出：true 解释：上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。 根节点的值为 True ，所以我们返回 true 。
示例 2：
输入：root = [0] 输出：false 解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
提示：
- 树中节点数目在
[1, 1000]之间。 0 <= Node.val <= 3- 每个节点的孩子数为
0或2。 - 叶子节点的值为
0或1。 - 非叶子节点的值为
2或3。
2.2 思路：
简单题，翻译一下题目的意思就可以了。
2.3 题解：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean evaluateTree(TreeNode root) {
return dfs(root);
}
private boolean dfs(TreeNode node) {
// 访问到了叶子节点,节点的值是0，就返回false，是1，就返回true
if(node.left == null && node.right == null){
return node.val == 0 ? false : true;
} else {
// 如果是一般节点，节点的值是2，就||左右子树的返回值
// 如果节点值是3，局&&左右子树的返回值
return node.val == 2 ? dfs(node.left) || dfs(node.right) : dfs(node.left) && dfs(node.right);
}
}
}3. 力扣100：相同的树
3.1 题目：
给你两棵二叉树的根节点 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
3.2 思路：
两棵树同时递归，判断指向的节点的关系即可。
3.3 题解：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return dfs(p, q);
}
private boolean dfs(TreeNode node1, TreeNode node2) {
// node1 == null && node2 == null这种情况直接返回true，没啥好说的
// 下一个循环是，当node1递归到null值时，node2还在递归节点
// 递归进度都不一样，两个树肯定不相同啊，直接反回false。
if(node1 == null && node2 == null){
return true;
}else if (node1 == null && node2 != null || node2 == null && node1 != null){
return false;
}
// 一般节点的情况，返回两个节点的值是否一样，以及考虑它的左右子树的情况
return node1.val == node2.val && dfs(node1.left, node2.left) && dfs(node1.right, node2.right);
}
}4. 力扣1379：找出克隆二叉树中的相同节点
4.1 题目：
给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
其中，克隆树 cloned 是原始树 original 的一个 副本 。
请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
示例 1:
输入: tree = [7,4,3,null,null,6,19], target = 3 输出: 3 解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。
示例 2:
输入: tree = [7], target = 7 输出: 7
示例 3:
输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 输出: 4
提示：
- 树中节点的数量范围为
[1, 104]。 - 同一棵树中，没有值相同的节点。
target节点是树original中的一个节点，并且不会是null。
进阶：如果树中允许出现值相同的节点，将如何解答？
4.2 思路：
我不知道题目方法中给个original有啥作用。
直接递归开找就行。
4.3 题解：
class Solution {
// 全局变量，将它指向在cloned树中我们要寻找的节点
// 在方法中直接返回
TreeNode prot;
public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
dfs(cloned, target);
return prot;
}
private void dfs(TreeNode node, final TreeNode target){
if(node == null){
return;
}
// 如果当前node指向的值和target的值相等，说明我们找到了
// 更新prot的值并返回
if(node.val == target.val){
prot = node;
return;
}else{
// 否则就继续在node的左右子树中查找
dfs(node.left, target);
dfs(node.right, target);
}
}
}原文地址：https://blog.csdn.net/2301_80912559/article/details/142313428
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！