Leetcode993 Cousins in Binary Tree

题目描述

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

1 2	Input: root = [1,2,3,4], x = 4, y = 3 Output: false

Example 2:

1 2	Input: root = [1,2,3,null,4,null,5], x = 5, y = 4 Output: true

Example 3:

1 2	Input: root = [1,2,3,null,4], x = 2, y = 3 Output: false

思路

判断条件：亲代不是同一个节点且深度相同。

代码

/**
 * 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 {
    static int i;
    static int j;
    static TreeNode dx;
    static TreeNode dy;
    public boolean isCousins(TreeNode root, int x, int y) {
        preorder(root,x, y, null,0);
        return dx!=dy&&i==j;
    }
    private static void preorder(TreeNode root, int x, int y, TreeNode p, int d){
        if(root==null) return;
        if(root.val==x){
            dx=p;
            i=d;
        }
        if(root.val==y){
            dy=p;
            j=d;
        }
        preorder(root.left,x,y,root,d+1);
        preorder(root.right,x,y,root,d+1);
            
    }
}