判斷二叉樹的堂兄弟節點BFS+dfs

DFS

class Solution {
    int x, y;
    int depthX, depthY;
    TreeNode fatherX, fatherY;
    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        getNodeDepthAndHisFather(root, null, 0);
        return (depthX == depthY) && (fatherX != fatherY);
    }
    void getNodeDepthAndHisFather(TreeNode root, TreeNode father, int depth){
        if(root == null) {return;}
        if(root.val == x) {
            this.depthX = depth;
            this.fatherX = father;
        }
        if(root.val == y) {
            this.depthY = depth;
            this.fatherY = father;
        }
        getNodeDepthAndHisFather(root.left, root, depth+1);
        getNodeDepthAndHisFather(root.right, root, depth+1);
    }
}
           

BFS
           

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) {
                    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;
    }