LeetCode 965.单值二叉树 python/scala

Univalued Binary Tree

环境：python 3.6，scala 2.11.8

题意

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

分析

• 不做叙述，理解并掌握二叉树的前、中、后序遍历即可；

• 此题的几种 scala 写法比较常用（isUnivalTree1、isUnivalTree3、isUnivalTree4），其中第四种写法体现层次遍历思路，类似的 scala 层次遍历写法可参考二叉树的层序遍历、二叉树的最小深度、层数最深叶子节点之和；

代码

python

def isUnivalTree(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root: return True
    value = root.val

    def dfs(node):
        if not node: return True # 这里的判断需要注意
        if node.val != value: return False
        return dfs(node.left) and dfs(node.right)
    return dfs(root)


# 先序
def isUnivalTreeV2(root):
    if not root: return False
    value = root.val
    stack = [root]
    while stack:
        curr = stack.pop()
        if curr:
            if curr.val != value: return False
            stack.append(curr.right)
            stack.append(curr.left)
    return True

scala

import scala.collection.mutable.Queue

object LC965 {
  def isUnivalTree(root: TreeNode): Boolean = {
    if (root == null) return true
    val value = root.value

    def dfs(node: TreeNode): Boolean = {
      if (node == null) true
      else if (node.value != value) false
      else dfs(node.left) & dfs(node.right)
    }
    dfs(root)
  }

  def isUnivalTree1(root: TreeNode): Boolean = {
    def dfs(node: TreeNode): Boolean = node match {
      case null => true
      case _ =>
        if (node.value != root.value) false
        else dfs(node.left) & dfs(node.right)
    }
    dfs(root)
  }

  def isUnivalTreeV2(root: TreeNode): Boolean = {
    if (root == null) return true
    val value = root.value
    val q = Queue[TreeNode](root)

    while (!q.isEmpty) {
      val curr = q.dequeue()
      if (curr != null) {
        if (curr.value != value) return false
        q.enqueue(curr.left)
        q.enqueue(curr.right)
      }
    }
    true
  }

  // 仍是队列的思路
  def isUnivalTreeV3(root: TreeNode): Boolean = {
    def go(currList: List[TreeNode]): Boolean = currList match {
      case Nil => true
      case h :: tail if h == null => go(tail)
      case h :: _ if h.value != root.value => false
      case h :: tail =>   go(tail ::: List(h.left, h.right))
    }
    go(List(root))
  }

  // 层次遍历思路
  def isUnivalTreeV4(root: TreeNode): Boolean = {
    def go(currList: List[TreeNode]): Boolean = currList match {
      case Nil => true
      case _ =>
        val nextLevel = currList.flatMap{node => List(node.left, node.right)}.filter(_ != null)
        if (nextLevel.exists(_.value != root.value)) false
        else go(nextLevel)
    }
    go(if (root == null) Nil else List(root))
  }
}

最后

欢迎交流和补充