截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
public boolean isCousins(TreeNode root, int x, int y) {
//兩個佇列一個存放樹的節點，一個存放節點對應的值
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> value = new LinkedList<>();
queue.add(root);
value.add(root.val);
//如果佇列不為空，說明樹的節點沒有遍歷完，就繼續遍歷
while (!queue.isEmpty()) {
//BFS是從上到下一層一層的列印，levelSize表示
//當前層的節點個數
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
//節點和節點值同時出隊
TreeNode poll = queue.poll();
value.poll();
//首先判斷x和y是否是兄弟節點的值，也就是判斷他們的父節點
//是否是同一個
if (poll.left != null && poll.right != null) {
//如果是親兄弟節點，直接回傳false
if ((poll.left.val == x && poll.right.val == y) ||
(poll.left.val == y && poll.right.val == x)) {
return false;
}
}
//左子節點不為空加入到佇列中
if (poll.left != null) {
queue.offer(poll.left);
value.offer(poll.left.val);
}
//右子節點不為空加入到佇列中
if (poll.right != null) {
queue.offer(poll.right);
value.offer(poll.right.val);
}
}
//判斷當前層是否包含這兩個節點的值，如果包含就是堂兄弟節點
if (value.contains(x) && value.contains(y))
return true;
}
return false;
}
時間復雜度：O(n)，n是節點的個數，最差情況下遍歷到最后一層，
空間復雜度：O(n)，使用兩個佇列，佇列中一個存放的是節點，一個存放的是節點的值，
private TreeNode xParent = null;//x的父節點
private TreeNode yParent = null;//y的父節點
private int xDepth = -1;//x的深度
private int yDepth = -2;//y的深度
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root, null, x, y, 0);
//如果他倆的深度一樣，也就是在同一層，又不是同一個父親，那么他倆
//就是堂兄弟節點，否則不是
return xDepth == yDepth && xParent != yParent ? true : false;
}
public void dfs(TreeNode root, TreeNode parent, int x, int y, int depth) {
if (root == null)
return;
if (root.val == x) {
//如果找到了x節點，就把他的父節點和深度記錄下來
xParent = parent;
xDepth = depth;
} else if (root.val == y) {
//如果找到了y節點，就把他的父節點和深度記錄下來
yParent = parent;
yDepth = depth;
}
//如果確定他倆是堂兄弟節點了，直接回傳，不用再往下遍歷了
if (xDepth == yDepth && xParent != yParent)
return;
dfs(root.left, root, x, y, depth + 1);
dfs(root.right, root, x, y, depth + 1);
}
時間復雜度：O(n)，n是節點的個數，最差情況下遍歷所有節點，
空間復雜度：O(n)，堆疊的深度，最壞情況下二叉樹退化為鏈表形狀，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300230.html
標籤：java
上一篇：【演算法學習】1863. 找出所有子集的異或總和再求和（java / c / c++ / python / go / rust）
下一篇：java 自動拆裝箱特性