LeetCode - Easy - 101. Symmetric Tree

素颜马尾好姑娘i 2022-12-28 04:06 120阅读 0赞

## Topic ##

*  Tree
 *  Depth-First Search
 *  Breadth-first Search

## Description ##

[https://leetcode.com/problems/symmetric-tree/][https_leetcode.com_problems_symmetric-tree]

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree \[1,2,2,3,4,4,3\] is symmetric:

1
       / \
      2   2
     / \ / \
    3  4 4  3

But the following \[1,2,2,null,3,null,3\] is not:

1
       / \
      2   2
       \   \
       3    3

Follow up: Solve it both recursively and iteratively.

## Analysis ##

方法一：BFS

方法二：DFS（递归）

## Submission ##

import java.util.Arrays;
    import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SymmetricTree { 
    
    	//方法一:我写的BFS
    	public boolean isSymmetric1(TreeNode root) { 
    		if (root == null) return true;
    		LinkedList<TreeNode> queue = new LinkedList<>(Arrays.asList(root.left, root.right));
    
    		while (!queue.isEmpty()) { 
    			int length = queue.size();
    
    			for (int i = 0, j = length - 1; i < length / 2; i++, j--) { 
    				TreeNode tn1 = queue.get(i);
    				TreeNode tn2 = queue.get(j);
    
    				if (tn1 == null && tn2 != null || tn1 != null && tn2 == null) { 
    					return false;
    				}
    
    				if (tn1 != null && tn2 != null) { 
    					if (tn1.val != tn2.val) { 
    						return false;
    					}
    				}
    			}
    
    			for(int i = length - 1; i >= 0; i--) { 
    				TreeNode node = queue.get(i);
    				queue.remove(i);
    				if(node != null)
    					queue.addAll(i, Arrays.asList(node.left, node.right));
    			}
    		}
    		return true;
    	}
    
    	//方法一:别人写的BFS
    	public boolean isSymmetric2(TreeNode root) { 
    		if (root == null) return true;
    		LinkedList<TreeNode> q = new LinkedList<>(Arrays.asList(root.left, root.right));
    		while (!q.isEmpty()) { 
    			TreeNode left = q.poll(), right = q.poll();
    			if (left == null && right == null) continue;
    			if (left == null || right == null || left.val != right.val) return false;
    			q.addAll(Arrays.asList(left.left, right.right, left.right, right.left));
    		}
    		return true;
    	}
    	
    	//方法二：
    	public boolean isSymmetric3(TreeNode root) { 
    		return root == null || isSymmetric3(root, root);
    	}
    	
    	private boolean isSymmetric3(TreeNode root1, TreeNode root2) { 
    		if(root1 == null && root2 != null || root1 != null && root2 == null)
    			return false;
    		
    		if(root1 != null && root2 != null) { 
    			
    			if(root1.val != root2.val) { 
    				return false;
    			}
    			return isSymmetric3(root1.left, root2.right) && isSymmetric3(root1.right, root2.left);
    		}
    		
    		return true;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    
    import org.junit.Before;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SymmetricTreeTest { 
    
    	private TreeNode root = null;
    	
    	@Before
    	public void init() { 
    		root = new TreeNode(1);
    		root.left = new TreeNode(2);
    		root.right = new TreeNode(2);
    	}
    	
    	
    	@Test
    	public void test1() { 
    		SymmetricTree obj = new SymmetricTree();
    
    		root.left.left = new TreeNode(3);
    		root.left.right = new TreeNode(4);
    		root.right.left = new TreeNode(4);
    		root.right.right = new TreeNode(3);
    		
    		assertTrue(obj.isSymmetric1(root));
    		assertTrue(obj.isSymmetric2(root));
    		assertTrue(obj.isSymmetric3(root));
    	}
    	
    	@Test
    	public void test2() { 
    		SymmetricTree obj = new SymmetricTree();
    		
    		root.left.right = new TreeNode(3);
    		root.right.right = new TreeNode(3);
    		
    		assertFalse(obj.isSymmetric1(root));
    		assertFalse(obj.isSymmetric2(root));
    		assertFalse(obj.isSymmetric3(root));
    	}
    }

[https_leetcode.com_problems_symmetric-tree]: https://leetcode.com/problems/symmetric-tree/