LeetCode.993-二叉樹中的堂兄弟(Cousins in Binary Tree)

這是悅樂書的第374次更新，第401篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

題（順位題号是

）。在二叉樹中，根節點在深度0處，并且每個深度為

的節點的子節點，他們深度為

k + 1

。

如果二進制樹的兩個節點具有相同的深度但具有不同的父節點，則它們是堂兄弟。

我們給出了具有唯一值的二叉樹

root

，以及樹中兩個不同節點的值

和

當且僅當對應于值x和y的節點是堂兄弟時，才傳回

true

。例如：

輸入：root = [1,2,3,4]，x = 4，y = 3

輸出：false

輸入：root = [1,2,3，null，4，null，5]，x = 5，y = 4

輸出：true

輸入：root = [1,2,3，null，4]，x = 2，y = 3

注意：

樹中的節點數将介于2和100之間。
每個節點都有一個從1到100的唯一整數值。

02 第一種解法

題目的意思是

在同一層，但是他們的父級節點不一樣，也就是

屬于堂兄弟的關系。

使用BFS（廣度優先）的算法，通過疊代的方式借助

Stack

來實作，使用了一個額外的方法，分别求出

的層級和他們的父級節點，用一個長度為2的數組傳回，如果

的層級相同且父級結點不同，就傳回

true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins(TreeNode root, int x, int y) {
    int[] arr = getTreeDepth(root, x);
    int[] arr2 = getTreeDepth(root, y);
    if (arr.length < 1 || arr2.length < 1) {
        return false;
    }
    return arr[0] != arr2[0] && arr[1] == arr2[1];
}

public int[] getTreeDepth(TreeNode root, int num) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    int depth = 0;
    while (!stack.isEmpty()) {
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem.left != null) {
                // 目前節點的左子節點值等于要找的數
                if (tem.left.val == num) {
                    return new int[] {tem.val, depth+1};
                }
                stack2.push(tem.left);
            }
            if (tem.right != null) {
                // 目前節點的右子節點值等于要找的數
                if (tem.right.val == num) {
                    return new int[] {tem.val, depth+1};
                }
                stack2.push(tem.right);
            }
        }
        stack = stack2;
        depth++;
    }
    return new int[] {};
}

03 第二種解法

針對第一種解法，我們也可以将判斷的方法融合在一起，依舊是借助棧。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins2(TreeNode root, int x, int y) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        boolean xExist = false, yExist = false;
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem.val == x) {
                xExist = true;
            }
            if (tem.val == y) {
                yExist = true;
            }
            // x和y不能有同一個父節點
            if (tem.left != null && tem.right != null) {
                if (tem.left.val == x && tem.right.val == y) {
                    return false;
                }
                if (tem.left.val == y && tem.right.val == x) {
                    return false;
                }
            }
            if (tem.left != null) {
                stack2.push(tem.left);
            }
            if (tem.right != null) {
                stack2.push(tem.right);
            }
        }
        stack = stack2;
        if (xExist && yExist) {
            return true;
        }
    }
    return false;
}

04 第三種解法

和第二種解法思路一樣，隻是将棧換成了隊列。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins3(TreeNode root, int x, int y) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        boolean xExist = false, yExist = false;
        for (int i=0; i<size; i++) {
            TreeNode tem = queue.poll();
            if (tem.val == x) {
                xExist = true;
            }
            if (tem.val == y) {
                yExist = true;
            }
            // x和y不能有同一個父節點
            if (tem.left != null && tem.right != null) {
                if (tem.left.val == x && tem.right.val == y) {
                    return false;
                }
                if (tem.left.val == y && tem.right.val == x) {
                    return false;
                }
            }
            if (tem.left != null) {
                queue.offer(tem.left);
            }
            if (tem.right != null) {
                queue.offer(tem.right);
            }
        }
        if (xExist && yExist) {
            return true;
        }
    }
    return false;
}

05 第四種解法

借助遞歸，一個遞歸方法求深度，一個遞歸方法找父節點，最後判斷深度是否相同且父節點不同。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins4(TreeNode root, int x, int y) {
    return getDepth(root, x, 0) == getDepth(root, y, 0) && 
            findParent(root, x) != findParent(root, y);
}

public int getDepth(TreeNode root, int num, int depth){
    if (root == null) {
        return 0;
    }
    if (root.val == num) {
        return depth;
    }
    int left = getDepth(root.left, num, depth+1);
    int right = getDepth(root.right, num, depth+1);
    return Math.max(left, right);
}

public int findParent(TreeNode root, int num) {
    if (root == null) {
        return 0;
    }
    if (root.left != null && root.left.val == num) {
        return root.val;
    }
    if (root.right != null && root.right.val == num) {
        return root.val;
    }
    int left = findParent(root.left, num);
    int right = findParent(root.right, num);
    return Math.max(left, right);
}

06 第五種解法

我們也可以隻是用一次遞歸方法，借助全局變量來解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

private int depthX;
private int depthY;
private TreeNode parentX;
private TreeNode parentY;

public boolean isCousins5(TreeNode root, int x, int y) {
    helper(root, x, y, 0, null);
    return depthX == depthY && parentX != parentY;
}

public void helper(TreeNode root, int x, int y, int depth, TreeNode parent) {
    if (root == null) {
        return ;
    }
    if (root.val == x) {
        depthX = depth;
        parentX = parent;
    } else if (root.val == y) {
        depthY = depth;
        parentY = parent;
    }
    helper(root.left, x, y, depth+1, root);
    helper(root.right, x, y, depth+1, root);
}

07 第六種解法

我們還可以将第五種解法中找父節點的變量換成

int

類型，因為節點值唯一，可以直接使用節點值參與判斷。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

private int depthX;
private int depthY;
private int parentX;
private int parentY;

public boolean isCousins6(TreeNode root, int x, int y) {
    helper(root, x, y, 0, 0);
    return depthX == depthY && parentX != parentY;
}

public void helper(TreeNode root, int x, int y, int depth, int parent) {
    if (root == null) {
        return ;
    }
    if (root.val == x) {
        depthX = depth;
        parentX = parent;
    } else if (root.val == y) {
        depthY = depth;
        parentY = parent;
    }
    helper(root.left, x, y, depth+1, root.val);
    helper(root.right, x, y, depth+1, root.val);
}

08 小結

算法專題目前已連續日更超過七個月，算法題文章241+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！

LeetCode.993-二叉樹中的堂兄弟(Cousins in Binary Tree)

01 看題和準備

02 第一種解法

03 第二種解法

04 第三種解法

05 第四種解法

06 第五種解法

07 第六種解法

08 小結

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

LeetCode-110-平衡二叉樹-C語言

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

LeetCode OJ Binary Tree Right Side View

leetcode809

hdu7108哈希