[每日 LeetCode] 993. Cousins in Binary Tree

原文链接 [每日 LeetCode] 993. Cousins in Binary Tree

Description

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:

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

Example 2:

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

Example 3:

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

思路：本题的意思为：定义二叉树中的“堂兄弟”结点，即两个深度相同且父结点不同的结点。给定一棵结点值互异的二叉树和两个树中的结点值 x 和 y ，问这两个结点是否为堂兄弟。只要遍历二叉树，并记录对应的两个结点的父节点和深度即可。遍历时注意以下三点：

• 仅在当前节点既不是 x 或 y 时遍历。
• 如果 x 是 y 的孩子，则不会遍历 y，直接返回 false。 y 的深度将始终保持默认值，即零。
• 如果 x 和 y 属于同一个父母，我们可以很容易地检查父母是否相同。

这是第二个代码跑出了 0ms。超过了 100% 的提交。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int x_depth,y_depth,x_parent,y_parent;
    bool isCousins(TreeNode* root, int x, int y) {
        isCousins_sub(root,x,y,0,root->val);
        if ((x_depth == y_depth) && (x_parent != y_parent))
            return true;
        else
            return false;
    }
    void isCousins_sub(TreeNode* root, int x, int y, int depth,int parent) {
        if(!root) return;
        depth++;
        if(root->val == x){
            x_depth = depth;
            x_parent = parent;
        }
        else if(root->val == y){
            y_depth = depth;
            y_parent = parent;
        }
        else{
            isCousins_sub(root->left,x,y,depth,root->val);
            isCousins_sub(root->right,x,y,depth,root->val);
        }
    }
};
​

运行时间：0ms

运行内存：11.4M