題目地址:993. 二叉樹的堂兄弟節(jié)點 - 力扣（LeetCode） (leetcode-cn.com)
思路：
我們可以從根節(jié)點開始，對樹進行一次遍歷，在遍歷的過程中維護「深度」以及「父節(jié)點」這兩個信息。當(dāng)我們遍歷到 xx 或 yy 節(jié)點時，就將信息記錄下來；當(dāng)這兩個節(jié)點都遍歷完成了以后，我們就可以退出遍歷的過程，判斷它們是否為堂兄弟節(jié)點了。
- 定義變量分別存儲x和y的信息
- 然后只需要在深度優(yōu)先搜索的遞歸函數(shù)中增加表示「深度」以及「父節(jié)點」的兩個參數(shù)即可。
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;
}
// 如果兩個節(jié)點都找到了，就可以提前退出遍歷
if (xFound && yFound) {
return;
}
dfs(node.left, depth + 1, node);
if (xFound && yFound) {
return;
}
dfs(node.right, depth + 1, node);
}
}
復(fù)雜度分析：
時間復(fù)雜度：O(n)，其中 nn 是樹中的節(jié)點個數(shù)。在最壞情況下，我們需要遍歷整棵樹，時間復(fù)雜度為 O(n)
空間復(fù)雜度：O(n)，即為深度優(yōu)先搜索的過程中需要使用的?？臻g。在最壞情況下，樹呈現(xiàn)鏈狀結(jié)構(gòu)，遞歸的深度為 O(n)。
題目地址:101. 對稱二叉樹 - 力扣（LeetCode） (leetcode-cn.com)
)
摘自一位評論區(qū)大佬的評論，看完點醒了我
問題可以轉(zhuǎn)化為：兩個樹在什么情況下互為鏡像？
如果同時滿足下面的條件，兩個樹互為鏡像：
- 它們的兩個根結(jié)點具有相同的值
- 每個樹的右子樹都與另一個樹的左子樹鏡像對稱
思路 遞歸法
定義節(jié)點1 節(jié)點2
先判斷節(jié)點1和節(jié)點2是否為空，是空，肯定是對稱的
如果 節(jié)點1為null或節(jié)點2為null 或 節(jié)點1的值！=節(jié)點2的值，那必然是不對稱
調(diào)用遞歸，通過 同步移動兩個指針方法，節(jié)點1和節(jié)點2指針 一開始都指向根節(jié)點，然后 節(jié)點1左移時，節(jié)點2右移，節(jié)點1右移，節(jié)點2左移，每次檢查當(dāng)前節(jié)點1和節(jié)點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);
}
}
復(fù)雜度分析
假設(shè)樹上一共 nn 個節(jié)點。
- 時間復(fù)雜度：這里遍歷了這棵樹，漸進時間復(fù)雜度為O(n)
- 空間復(fù)雜度：這里的空間復(fù)雜度和遞歸使用的棧空間有關(guān)，這里遞歸層數(shù)不超過n，故漸進空間復(fù)雜度為 O(n)
思路 迭代法
- 定義個隊列 先把根節(jié)點左右節(jié)點入隊列
- while循環(huán) 首先彈出兩個節(jié)點 node1 node2
- 判斷 node1和node2是否空 二者一為空 繼續(xù)
- 如果 節(jié)點1為null或節(jié)點2為null 或 節(jié)點1的值！=節(jié)點2的值，那必然是不對稱
- 將兩個結(jié)點的左右子結(jié)點按相反的順序插入隊列中
- 隊列為空時，或者我們檢測到樹不對稱（即從隊列中取出兩個不相等的連續(xù)結(jié)點）時，該算法結(jié)束
/**
* 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;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：這里遍歷了這棵樹，漸進時間復(fù)雜度為 O(n)
- 空間復(fù)雜度：這里需要用一個隊列來維護節(jié)點，每個節(jié)點最多進隊一次，出隊一次，隊列中最多不會超過n個點，故漸進空間復(fù)雜度為 O(n)
代碼均由力扣編譯器，提交通過，描述編寫不當(dāng)?shù)胤竭€請大家評論區(qū)指出??！
