LeetCode - Easy - 965. Univalued Binary Tree

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

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/univalued-binary-tree/][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:**

![d69d92fe4f185fc94c3a412acbbaca57.png][]

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

**Example 2:**

![6313e28f6155836b9eee2b2b8b9e40a5.png][]

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

**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]`.

## 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)));
    	}
    }

[https_leetcode.com_problems_univalued-binary-tree]: https://leetcode.com/problems/univalued-binary-tree/
[d69d92fe4f185fc94c3a412acbbaca57.png]: /images/20221005/c955b8c3c653424c9c7f33a8ceb62657.png
[6313e28f6155836b9eee2b2b8b9e40a5.png]: /images/20221005/53430188a3e54c5b9fa4b9150e9ca4a1.png