Easy

题目描述

给你二叉树的根节点 root 和两个整数 x 和 y，如果二叉树中值为 x 和 y 的两个节点是堂兄弟节点，则返回 true；否则，返回 false。

如果二叉树的两个节点深度相同但父节点不同，则它们是一对堂兄弟节点。

注意，在二叉树中，根节点深度为 0，每一层深度递增 1。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

提示：

  • 树中节点数的范围是 [2, 100]
  • 1 <= Node.val <= 100
  • 每个节点的值都是唯一的
  • x != y
  • x 和 y 都存在于树中

解题思路

解题思路

要判断两个节点是否为堂兄弟节点，需要满足两个条件：

  1. 两个节点的深度相同
  2. 两个节点的父节点不同

我们可以用两种方法来解决：

方法一：DFS（深度优先搜索） 使用递归遍历树，分别记录目标节点的深度和父节点。由于我们需要同时获取两个节点的信息，可以用一次遍历完成。

方法二：BFS（广度优先搜索） 使用队列进行层序遍历，对于每一层，检查是否包含目标节点，并记录它们的父节点信息。

两种方法的时间复杂度都是 O(n)，空间复杂度也都是 O(n)。这里推荐使用 DFS 方法，代码更简洁易懂。

核心思想是：在遍历过程中，当找到目标节点时，记录其深度和父节点。最后比较两个目标节点是否满足堂兄弟节点的条件。

代码实现

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        TreeNode* parentX = nullptr;
        TreeNode* parentY = nullptr;
        int depthX = -1, depthY = -1;
        
        dfs(root, nullptr, 0, x, y, parentX, parentY, depthX, depthY);
        
        return depthX == depthY && parentX != parentY;
    }
    
private:
    void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y,
             TreeNode*& parentX, TreeNode*& parentY, int& depthX, int& depthY) {
        if (!node) return;
        
        if (node->val == x) {
            parentX = parent;
            depthX = depth;
        }
        if (node->val == y) {
            parentY = parent;
            depthY = depth;
        }
        
        dfs(node->left, node, depth + 1, x, y, parentX, parentY, depthX, depthY);
        dfs(node->right, node, depth + 1, x, y, parentX, parentY, depthX, depthY);
    }
};

class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        def dfs(node, parent, depth):
            if not node:
                return
            
            if node.val == x:
                self.x_info = (parent, depth)
            elif node.val == y:
                self.y_info = (parent, depth)
            
            dfs(node.left, node, depth + 1)
            dfs(node.right, node, depth + 1)
        
        self.x_info = None
        self.y_info = None
        dfs(root, None, 0)
        
        x_parent, x_depth = self.x_info
        y_parent, y_depth = self.y_info
        
        return x_depth == y_depth and x_parent != y_parent

public class Solution {
    private TreeNode parentX, parentY;
    private int depthX = -1, depthY = -1;
    
    public bool IsCousins(TreeNode root, int x, int y) {
        DFS(root, null, 0, x, y);
        return depthX == depthY && parentX != parentY;
    }
    
    private void DFS(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) return;
        
        if (node.val == x) {
            parentX = parent;
            depthX = depth;
        }
        if (node.val == y) {
            parentY = parent;
            depthY = depth;
        }
        
        DFS(node.left, node, depth + 1, x, y);
        DFS(node.right, node, depth + 1, x, y);
    }
}

var isCousins = function(root, x, y) {
    let xInfo = null;
    let yInfo = null;
    
    function dfs(node, parent, depth) {
        if (!node) return;
        
        if (node.val === x) {
            xInfo = { parent, depth };
        } else if (node.val === y) {
            yInfo = { parent, depth };
        }
        
        if (xInfo && yInfo) return;
        
        dfs(node.left, node, depth + 1);
        dfs(node.right, node, depth + 1);
    }
    
    dfs(root, null, 0);
    
    return xInfo && yInfo && 
           xInfo.depth === yInfo.depth && 
           xInfo.parent !== yInfo.parent;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n)最坏情况下需要遍历整个二叉树的所有节点
空间复杂度O(h)递归调用栈的深度，h 为树的高度，最坏情况下为 O(n)

相关题目