LeetCode - Easy - 872. Leaf-Similar Trees

迈不过友情╰ 2022-10-06 06:54 47阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/leaf-similar-trees/][https_leetcode.com_problems_leaf-similar-trees]

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a **leaf value sequence**.

![3b1bb158ebe9c3147e974f1fae08048e.png][]

For example, in the given tree above, the leaf value sequence is `(6, 7, 4, 9, 8)`.

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes `root1` and `root2` are leaf-similar.

**Example 1:**  
![987b3a71579326526e70439d1a28470c.png][]

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
    Output: true

**Example 2:**

Input: root1 = [1], root2 = [1]
    Output: true

**Example 3:**

Input: root1 = [1], root2 = [2]
    Output: false

**Example 4:**

Input: root1 = [1,2], root2 = [2,2]
    Output: true

**Example 5:**

![57d48edb37912116d948fad8f5a26be3.png][]

Input: root1 = [1,2,3], root2 = [1,3,2]
    Output: false

**Constraints:**

*  The number of nodes in each tree will be in the range `[1, 200]`.
 *  Both of the given trees will have values in the range `[0, 200]`.

## Analysis ##

用到方便中断的迭代版前序遍历模式。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class LeafSimilarTrees { 
    	
        public boolean leafSimilar(TreeNode root1, TreeNode root2) { 
            
        	LinkedList<TreeNode> stack1 = new LinkedList<>(), //
        			stack2 = new LinkedList<>();
        	stack1.push(root1);
        	stack2.push(root2);
        	while(true) { 
        		TreeNode leaf1 = getLeaf(stack1);
        		TreeNode leaf2 = getLeaf(stack2);
        		
        		if(leaf1 == null ^ leaf2 == null) { 
        			return false;
        		}else if(leaf1 == null && leaf2 == null) { 
        			return true;
        		}else { 
        			if(leaf1.val != leaf2.val)
        				return false;
        		}
        	}
        }
        
        private TreeNode getLeaf(LinkedList<TreeNode> stack) { 
        	
    		while(!stack.isEmpty()) {     			
    			TreeNode node = stack.pop();
    			
    			if(node.left == null && node.right == null)
    				return node;
    			
    			if(node.right != null)
    				stack.push(node.right);
    			
    			if(node.left != null)
    				stack.push(node.left);
    		}
        	
        	return null;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.BinaryTree.integers2BinaryTree;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class LeafSimilarTreesTest { 
    
    	@Test
    	public void test() { 
    		LeafSimilarTrees obj = new LeafSimilarTrees();
    
    		TreeNode root1 = integers2BinaryTree(3,5,1,6,2,9,8,null,null,7,4);
    		TreeNode root2 = integers2BinaryTree(3,5,1,6,7,4,2,null,null,null,null,null,null,9,8);
    		
    		assertTrue(obj.leafSimilar(root1, root2));
    		assertTrue(obj.leafSimilar(integers2BinaryTree(1), integers2BinaryTree(1)));
    		assertFalse(obj.leafSimilar(integers2BinaryTree(1), integers2BinaryTree(2)));
    		assertTrue(obj.leafSimilar(integers2BinaryTree(1, 2), integers2BinaryTree(2, 2)));
    		assertFalse(obj.leafSimilar(integers2BinaryTree(1, 2, 3), integers2BinaryTree(1,3,2)));
    		assertFalse(obj.leafSimilar(integers2BinaryTree(3,5,1,6,7,4,2,null,null,null,null,null,null,9,11,null,null,8,10),// 
    						integers2BinaryTree(3,5,1,6,2,9,8,null,null,7,4)));
    	}
    }

[https_leetcode.com_problems_leaf-similar-trees]: https://leetcode.com/problems/leaf-similar-trees/
[3b1bb158ebe9c3147e974f1fae08048e.png]: /images/20221005/8bb9fa08567a4f92bf6acab564de52f2.png
[987b3a71579326526e70439d1a28470c.png]: /images/20221005/25febe145f694854a4b787fbf815697f.png
[57d48edb37912116d948fad8f5a26be3.png]: /images/20221005/db78871105a544aeb532425f4249505c.png