993. 二叉树的堂兄弟节点

993. 二叉树的堂兄弟节点

• 难度: easy
• 原始链接: https://leetcode.cn/problems/cousins-in-binary-tree
• 标签: 深度优先遍历, 广度优先遍历

解法一: 深度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
  xParentNode, xDepth := dfs(root, nil, 0, x)
  yParentNode, yDepth := dfs(root, nil, 0, y)
  return xParentNode != yParentNode && xDepth == yDepth
}

func dfs(curNode, parentNode *TreeNode, depth, target int) (int, int) {
  if curNode == nil {
    return -1, -1
  }
  if curNode.Val == target {
    if parentNode == nil {
      return 0, depth
    }
    return parentNode.Val, depth
  }
  if leftParentNode, leftDepth := dfs(curNode.Left, curNode, depth+1, target); leftParentNode != -1 {
    return leftParentNode, leftDepth
  }
  return dfs(curNode.Right, curNode, depth+1, target)
}

解法二: 广度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
  queue := []*TreeNode{root}
  for len(queue) > 0 {
    size := len(queue)
    flag := 0
    for _, node := range queue[:size] {
      preFlag := flag
      if node.Left != nil {
        curVal := node.Left.Val
        if curVal == x {
          flag |= 1
        }
        if curVal == y {
          flag |= 2
        }
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        curVal := node.Right.Val
        if curVal == x {
          flag |= 1
        }
        if curVal == y {
          flag |= 2
        }
        queue = append(queue, node.Right)
      }
      if flag == 3 {
        if preFlag == 0 {
          return false
        }
        return true
      }
    }
    queue = queue[size:]
  }
  return false
}