LeetCode 993. 二叉树的堂兄弟节点

Categories:

题目描述
思路分析
1. 解法一：BFS 层序遍历（推荐）
2. 解法二：DFS
相似题目

题目描述

✅ 993. 二叉树的堂兄弟节点

思路分析

解法一：BFS 层序遍历（推荐）

核心思路：

堂兄弟节点的定义：深度相同但父节点不同。

使用 BFS 逐层遍历，在同一层中找到两个目标节点的深度与父节点信息。

对每个节点，记录其深度和父节点，找到 x 和 y 对应的信息后，判断深度相同且父节点不同即为堂兄弟。

BFS 天然按层处理，可以在发现两个目标节点都在同一层时提前返回结果。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，最多遍历所有节点

空间复杂度：O(n)，BFS 队列最多存储一层的节点数

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        // 记录 x 和 y 的父节点和深度
        TreeNode xParent = null, yParent = null;
        int xDepth = 0, yDepth = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        Map<TreeNode, Integer> depthMap = new HashMap<>();

        queue.offer(root);
        parentMap.put(root, null);
        depthMap.put(root, 0);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int depth = depthMap.get(node);

            if (node.val == x) {
                xParent = parentMap.get(node);
                xDepth = depth;
            }
            if (node.val == y) {
                yParent = parentMap.get(node);
                yDepth = depth;
            }

            if (node.left != null) {
                parentMap.put(node.left, node);
                depthMap.put(node.left, depth + 1);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                depthMap.put(node.right, depth + 1);
                queue.offer(node.right);
            }
        }

        // 深度相同且父节点不同
        return xDepth == yDepth && xParent != yParent;
    }
}

func isCousins(root *TreeNode, x int, y int) bool {
    type NodeInfo struct {
        node   *TreeNode
        parent *TreeNode
        depth  int
    }

    var xParent, yParent *TreeNode
    xDepth, yDepth := -1, -1

    queue := []NodeInfo{{root, nil, 0}}

    for len(queue) > 0 {
        info := queue[0]
        queue = queue[1:]

        node, parent, depth := info.node, info.parent, info.depth

        if node.Val == x {
            xParent = parent
            xDepth = depth
        }
        if node.Val == y {
            yParent = parent
            yDepth = depth
        }

        if node.Left != nil {
            queue = append(queue, NodeInfo{node.Left, node, depth + 1})
        }
        if node.Right != nil {
            queue = append(queue, NodeInfo{node.Right, node, depth + 1})
        }
    }

    // 深度相同且父节点不同
    return xDepth == yDepth && xParent != yParent
}

解法二：DFS

核心思路：

通过 DFS 遍历整棵树，找到 x 和 y 各自的深度和父节点。

递归时传入当前节点的父节点和深度，遇到目标值时记录对应信息。

最终判断两者深度相同且父节点不同。

复杂度分析：

时间复杂度：O(n)，遍历所有节点

空间复杂度：O(n)，递归栈深度

class Solution {
    private int xDepth, yDepth;
    private TreeNode xParent, yParent;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return xDepth == yDepth && xParent != yParent;
    }

    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) {
            return;
        }

        if (node.val == x) {
            xDepth = depth;
            xParent = parent;
        }
        if (node.val == y) {
            yDepth = depth;
            yParent = parent;
        }

        dfs(node.left, node, depth + 1, x, y);
        dfs(node.right, node, depth + 1, x, y);
    }
}

func isCousins(root *TreeNode, x int, y int) bool {
    xDepth, yDepth := -1, -1
    var xParent, yParent *TreeNode

    var dfs func(node, parent *TreeNode, depth int)
    dfs = func(node, parent *TreeNode, depth int) {
        if node == nil {
            return
        }

        if node.Val == x {
            xDepth = depth
            xParent = parent
        }
        if node.Val == y {
            yDepth = depth
            yParent = parent
        }

        dfs(node.Left, node, depth+1)
        dfs(node.Right, node, depth+1)
    }

    dfs(root, nil, 0)
    return xDepth == yDepth && xParent != yParent
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS、二叉树
104. 二叉树的最大深度	简单	DFS、BFS
111. 二叉树的最小深度	简单	BFS、DFS
199. 二叉树的右视图	中等	BFS、DFS
513. 找树左下角的值	中等	BFS、DFS
637. 二叉树的层平均值	简单	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/87302493