在二叉树中查找表兄弟

Question

给定具有唯一值的二叉树的根以及树 x 和 y 的两个不同节点的值，如果树中与值 x 和 y 对应的节点是表兄弟，则返回 true，否则返回 false。

二叉树的两个节点是表兄弟，如果它们具有相同的深度且具有不同的父节点。

请注意，在二叉树中，根节点位于深度 0，每个深度 k 节点的子节点位于深度 k + 1。

限制：

树中的节点数在 [2, 100] 范围内。 1 <= Node.val <= 100 Each node has a unique value. x != y x and y are exist in the tree.

我创建了一个高度函数，它返回从根开始的节点的高度，并且我检查了 X 和 Y 的高度。 如果它们不同，我返回 false。 然后我创建了一个父函数，它返回节点的父节点。然后我检查父母是否相同返回 false 否则返回 true。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
int height(TreeNode* root,int x){
    if(root==NULL)
        return -1;
    if(root->val==x)
        return 1;
    int lh=height(root->left,x);
    int rh=height(root->right,x);

    if(lh!=-1)
        return lh+1;
    if(rh!=-1)
        return rh+1;
    
     return -1;
}

TreeNode* parent(TreeNode* root,int x){
    if(!root)
        return NULL;
    if(root->right && root->right->val==x )
        return root;
    if(root->left && root->left->val==x)
        return root;
    TreeNode* lh=parent(root->left,x);
    TreeNode* rh=parent(root->right,x);   
    if(!lh)
        return lh;
    if(!rh)
        return rh;
    
        return NULL;
}

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        //check if height of both are same
        int xh=height(root,x);
        int yh=height(root,y);
        if(xh!=yh)
            return 0;

        ///check if parents of both are same
        TreeNode* xp=parent(root,x);
        TreeNode* yp=parent(root,y);
        if(xp==yp)
            return 0;
        
        return 1;
    }
};

Answer 1

您的

parent

函数有错误：

这组语句将始终返回

NULL

:

    if(!lh)
        return lh;
    if(!rh)
        return rh;
    
        return NULL;

当节点引用不是

NULL

时，你需要返回一个节点引用。所以正确的是：

    if (lh)
        return lh;
    if (rh)
        return rh;
    
    return NULL;