LeetCode - Easy - 100. Same Tree

朴灿烈づ我的快乐病毒、 2022-12-28 00:59 139阅读 0赞

## Topic ##

Tree, Depth-first Search

## Description ##

[https://leetcode.com/problems/same-tree/][https_leetcode.com_problems_same-tree]

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

**Example 1**:

Input:     1         1
              / \       / \
             2   3     2   3
    
            [1,2,3],   [1,2,3]
    
    Output: true

**Example 2**:

Input:     1         1
              /           \
             2             2
    
            [1,2],     [1,null,2]
    
    Output: false

**Example 3**:

Input:     1         1
              / \       / \
             2   1     1   2
    
            [1,2,1],   [1,1,2]
    
    Output: false

## Analysis ##

方法一：递归前序遍历

方法二：非递归前序遍历

## Submission ##

import java.util.Arrays;
    import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SameTree { 
    
    	//方法一：递归前序遍历
        public boolean isSameTree1(TreeNode p, TreeNode q) { 
            if (p == null && q != null || p != null && q == null)
    			return false;
    
    		if (p != null && q != null) { 
    			if (p.val != q.val) { 
    				return false;
    			}
    
    			// 判断左右子树
    			return isSameTree1(p.left, q.left) && isSameTree1(p.right, q.right);
    		}
    
    		return true;
        }
        
        //方法二：非递归前序遍历
        public boolean isSameTree2(TreeNode root1, TreeNode root2) { 
        	TreeNode p = root1, q = root2;
        	
        	LinkedList<TreeNode> stack = new LinkedList<>();
        	
        	while(true) { 
        		if(p == null && q != null || p != null && q == null) { 
        			return false;
        		}
        		
        		if(p != null && q != null) { 
        			if(p.val != q.val) { 
        				return false;
        			}
        			
        			//下列push的精简
        			stack.addAll(0, Arrays.asList(p.left, q.left, p.right, q.right));
        			
    // stack.push(q.right);
    // stack.push(p.right);
    // 
    // stack.push(q.left);
    // stack.push(p.left);
        		}
        		
        		if(stack.isEmpty()) { 
        			break;
        		}else { 
        			p = stack.pop();
        			q = stack.pop();
        		}
        	}
        	
        	return true;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SameTreeTest { 
    
    	@Test
    	public void test() { 
    		SameTree obj = new SameTree();
    		
    		TreeNode root1 = new TreeNode(1);
    		root1.left = new TreeNode(2);
    		root1.right = new TreeNode(3);
    		
    		TreeNode root2 = new TreeNode(1);
    		root2.left = new TreeNode(2);
    		root2.right = new TreeNode(3);
    		
    		assertTrue(obj.isSameTree1(root1, root2));
    		assertTrue(obj.isSameTree2(root1, root2));
    	}
    	
    	@Test
    	public void test2() { 
    		SameTree obj = new SameTree();
    		
    		TreeNode root1 = new TreeNode(1);
    		root1.left = new TreeNode(2);
    		
    		TreeNode root2 = new TreeNode(1);
    		root2.right = new TreeNode(2);
    		
    		assertFalse(obj.isSameTree1(root1, root2));
    		assertFalse(obj.isSameTree2(root1, root2));
    	}
    	
    	@Test
    	public void test3() { 
    		SameTree obj = new SameTree();
    		
    		TreeNode root1 = new TreeNode(1);
    		root1.left = new TreeNode(2);
    		root1.right = new TreeNode(1);
    		
    		TreeNode root2 = new TreeNode(1);
    		root2.right = new TreeNode(1);
    		root2.right = new TreeNode(2);
    		
    		assertFalse(obj.isSameTree1(root1, root2));
    		assertFalse(obj.isSameTree2(root1, root2));
    	}
    }

[https_leetcode.com_problems_same-tree]: https://leetcode.com/problems/same-tree/