LeetCode - Easy - 572. Subtree of Another Tree

布满荆棘的人生 2022-10-15 00:37 13阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/subtree-of-another-tree/][https_leetcode.com_problems_subtree-of-another-tree]

Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of root with the same structure and node values of `subRoot` and `false` otherwise.

A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node’s descendants. The tree `tree` could also be considered as a subtree of itself.

**Example 1:**

![1e5f9bb5fade74e48cd8a6299a897fbc.png][]

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
    Output: true

**Example 2:**

![e17842c72af0219ea0936205429eacde.png][]

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
    Output: false

**Constraints:**

*  The number of nodes in the `root` tree is in the range \[1, 2000\].
 *  The number of nodes in the `subRoot` tree is in the range \[1, 1000\].
 *   − 1 0 4 < = r o o t . v a l < = 1 0 4 -10^4 <= root.val <= 10^4 −104<=root.val<=104
 *   − 1 0 4 < = s u b R o o t . v a l < = 1 0 4 -10^4 <= subRoot.val <= 10^4 −104<=subRoot.val<=104

## Analysis ##

考查前序遍历。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class SubtreeOfAnotherTree { 
        public boolean isSubtree(TreeNode root, TreeNode subRoot) { 
        	if(root == null ^ subRoot == null)
        		return false;
        	
            if(equals(root, subRoot))
            	return true;
    
        	return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        }
        
        public boolean equals(TreeNode node1, TreeNode node2) { 
        	if(node1 == null ^ node2 == null)
        		return false;
        	
        	if(node1 != null && node2 != null) { 
        		if(node1.val != node2.val) 
        			return false;
    
        		return equals(node1.left, node2.left) && //
        				equals(node1.right, node2.right);
        	}
        	return true;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.BinaryTree.*;
    import org.junit.Test;
    
    
    public class SubtreeOfAnotherTreeTest { 
    
    	@Test
    	public void test() { 
    		SubtreeOfAnotherTree obj = new SubtreeOfAnotherTree();
    
    		assertTrue(obj.isSubtree(integers2BinaryTree(3, 4, 5, 1, 2), //
    				integers2BinaryTree(4, 1, 2)));
    		
    		assertFalse(obj.isSubtree(integers2BinaryTree(3, 4, 5, 1, 2, null, null, null, null, 0),// 
    				integers2BinaryTree(4, 1, 2)));
    	}
    }

[https_leetcode.com_problems_subtree-of-another-tree]: https://leetcode.com/problems/subtree-of-another-tree/
[1e5f9bb5fade74e48cd8a6299a897fbc.png]: /images/20221014/0e56a4e73b8e4c9b9c74d3337f03bde8.png
[e17842c72af0219ea0936205429eacde.png]: /images/20221014/ccd248d445a042eb802c4eb99115653c.png