LeetCode - Easy - 965. Univalued Binary Tree-蒲公英云

LeetCode - Easy - 965. Univalued Binary Tree

r囧r小猫 2022-10-06 05:49 74阅读 0赞

Topic

Tree

Description

https://leetcode.com/problems/univalued-binary-tree/

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

Example 2:

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

Note:

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

Analysis

方法一：递归法

方法二：迭代法

Submission

import java.util.LinkedList;
import com.lun.util.BinaryTree.TreeNode;
public class UnivaluedBinaryTree { 
    //方法一：递归法
    public boolean isUnivalTree(TreeNode root) { 
        if(root == null) return true;
        if(root.left != null && root.left.val != root.val)
            return false;
        if(root.right != null && root.right.val != root.val)
            return false;
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }
    //方法二：迭代法
    public boolean isUnivalTree2(TreeNode root) { 
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()) { 
            TreeNode node = stack.pop();
            if(node.left != null) { 
                if(node.left.val != root.val)
                    return false;
                stack.push(node.left);
            }
            if(node.right != null) { 
                if(node.right.val != root.val)
                    return false;
                stack.push(node.right);
            }
        }
        return true;
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class UnivaluedBinaryTreeTest { 
    @Test
    public void test() { 
        UnivaluedBinaryTree obj = new UnivaluedBinaryTree();
        assertTrue(obj.isUnivalTree(BinaryTree.integers2BinaryTree(1,1,1,1,1,null,1)));
        assertFalse(obj.isUnivalTree(BinaryTree.integers2BinaryTree(2,2,2,5,2)));
    }
    @Test
    public void test2() { 
        UnivaluedBinaryTree obj = new UnivaluedBinaryTree();
        assertTrue(obj.isUnivalTree2(BinaryTree.integers2BinaryTree(1,1,1,1,1,null,1)));
        assertFalse(obj.isUnivalTree2(BinaryTree.integers2BinaryTree(2,2,2,5,2)));
    }
}