993. Cousins in Binary Tree

Leetcode 链接

题目

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

Note:

The number of nodes in the tree will be between 2 and 100. Each node has a unique integer value from 1 to 100.

题意解析

当两个节点无共同父节点并且处于树种的同一层时称之为 cousin 节点，题中给出两个节点，判断这两个节点是否为 cousin。

解决方案

设定一个全局 Map 记录每个节点的层高以及父节点信息，对树进行遍历，当两个节点都找到时就可以退出遍历工作。

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Position struct{
    Level int
    Parent int
}

var depthMap map[int]*Position

func isCousins(root *TreeNode, x int, y int) bool {
    if root == nil || (root != nil && root.Left == nil) || (root != nil && root.Right == nil) {
        return false
    }

    depthMap = make(map[int]*Position)
    help(root, -1, 0, x, y)

    return (depthMap[x].Level == depthMap[y].Level) && (depthMap[x].Parent != depthMap[y].Parent)
}

func help(root *TreeNode, parent, level, x, y int) {
    if root == nil{
        return 
    }

    switch {
        case root.Val == x:
        depthMap[x] = &Position{
            Level : level,
            Parent : parent,
        }

        case root.Val == y:
        depthMap[y] = &Position{
            Level: level,
            Parent: parent,
        }        
    }

    if depthMap[x] != nil && depthMap[y] != nil{
        return
    }

    help(root.Left, root.Val, level+1, x, y)
    help(root.Right, root.Val, level+1, x, y)
}