Leetcode: Univalued Binary Tree

Univalued Binary Tree



Similar Problems:


A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]
Output: true

Leetcode: Univalued Binary Tree

Example 2:

Input: [2,2,2,5,2]
Output: false

Leetcode: Univalued Binary Tree

Note:

  1. The number of nodes in the given tree will be in the range [1, 100].
  2. Each node’s value will be an integer in the range [0, 99].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • With mini function
// Blog link: https://code.dennyzhang.com/univalued-binary-tree
// Basic Ideas: pre-order tree traseveral
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func visit(root *TreeNode, value int) bool {
    if root == nil { return true }
    if root.Val != value { return false }
    return visit(root.Left, value) && visit(root.Right, value)
}

func isUnivalTree(root *TreeNode) bool {
    if root == nil { return true }
    return visit(root.Left, root.Val) && visit(root.Right, root.Val)
}

  • Without mini function
// Blog link: https://code.dennyzhang.com/univalued-binary-tree
// Basic Ideas: pre-order tree traseveral
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isUnivalTree(root *TreeNode) bool {
    if root == nil { return true }
    if root.Left != nil && root.Val != root.Left.Val {
        return false
    }
    if root.Right != nil && root.Val != root.Right.Val {
        return false
    }
    return isUnivalTree(root.Left) && isUnivalTree(root.Right)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.