题目地址:993. 二叉树的堂兄弟节点 - 力扣（LeetCode） (leetcode-cn.com)
image
思路：
我们可以从根节点开始，对树进行一次遍历，在遍历的过程中维护「深度」以及「父节点」这两个信息。当我们遍历到 xx 或 yy 节点时，就将信息记录下来；当这两个节点都遍历完成了以后，我们就可以退出遍历的过程，判断它们是否为堂兄弟节点了。
- 定义变量分别存储x和y的信息
- 然后只需要在深度优先搜索的递归函数中增加表示「深度」以及「父节点」的两个参数即可。
class Solution {
// x 的信息
int x;
TreeNode xParent;
int xDepth;
boolean xFound = false;
// y 的信息
int y;
TreeNode yParent;
int yDepth;
boolean yFound = false;
public boolean isCousins(TreeNode root, int x, int y) {
this.x = x;
this.y = y;
dfs(root, 0, null);
return xDepth == yDepth && xParent != yParent;
}
public void dfs(TreeNode node, int depth, TreeNode parent) {
if (node == null) {
return;
}
if (node.val == x) {
xParent = parent;
xDepth = depth;
xFound = true;
} else if (node.val == y) {
yParent = parent;
yDepth = depth;
yFound = true;
}
// 如果两个节点都找到了，就可以提前退出遍历
if (xFound && yFound) {
return;
}
dfs(node.left, depth + 1, node);
if (xFound && yFound) {
return;
}
dfs(node.right, depth + 1, node);
}
}
复杂度分析：
时间复杂度：O(n)，其中 nn 是树中的节点个数。在最坏情况下，我们需要遍历整棵树，时间复杂度为 O(n)
空间复杂度：O(n)，即为深度优先搜索的过程中需要使用的栈空间。在最坏情况下，树呈现链状结构，递归的深度为 O(n)。
题目地址:101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)
image
)
摘自一位评论区大佬的评论，看完点醒了我
image
问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
思路 递归法
定义节点1 节点2
先判断节点1和节点2是否为空，是空，肯定是对称的
如果 节点1为null或节点2为null 或 节点1的值！=节点2的值，那必然是不对称
调用递归，通过 同步移动两个指针方法，节点1和节点2指针 一开始都指向根节点，然后 节点1左移时，节点2右移，节点1右移，节点2左移，每次检查当前节点1和节点2的值 是否相等，相等再判断是否对称左右子树
/**
* 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 isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return cmp(root.right,root.left);
}
public boolean cmp(TreeNode node1,TreeNode node2){
if(node1==null&&node2==null){
return true;
}
if(node1==null||node2==null||node1.val!=node2.val){
return false;
}
return cmp(node1.left,node2.right) && cmp(node2.left,node1.right);
}
}
复杂度分析
假设树上一共 nn 个节点。
- 时间复杂度：这里遍历了这棵树，渐进时间复杂度为O(n)
- 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过n，故渐进空间复杂度为 O(n)
思路 迭代法
- 定义个队列 先把根节点左右节点入队列
- while循环 首先弹出两个节点 node1 node2
- 判断 node1和node2是否空 二者一为空 继续
- 如果 节点1为null或节点2为null 或 节点1的值！=节点2的值，那必然是不对称
- 将两个结点的左右子结点按相反的顺序插入队列中
- 队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束
/**
* 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 isSymmetric(TreeNode root) {
if(root==null){
return true;
}
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()){
TreeNode node1=queue.poll();
TreeNode node2=queue.poll();
if(node1==null&&node2==null){
continue;
}
if(node1==null||node2==null||node1.val!=node2.val){
return false;
}
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node2.left);
queue.offer(node1.right);
}
return true;
}
}
复杂度分析
- 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)
- 空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过n个点，故渐进空间复杂度为 O(n)
代码均由力扣编译器，提交通过，描述编写不当地方还请大家评论区指出💪！
