学步园

  A very interesting problem. At first if you have no idea how to do it, it will be very difficult. Once you got it, you will find out that you only need to traverse the tree twice. First is travelling the tree with left-child
first, the other is right child first. If their outputs are the same, its symmetric tree. Mark: you need to add an tag to mark the value, to see if they are left child or right child. 

import java.util.*;

public class Solution {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		public TreeNode(int x) {
			val = x;
		}
	}
	
	public void PreTrav_Left(TreeNode node, ArrayList<Double> vals, double added)
	{
		vals.add(node.val+added);
		
		if(node.left != null)
		{
			PreTrav_Left(node.left, vals, 0.4);
		}
		
		if(node.right != null)
		{
			PreTrav_Left(node.right,vals, 0.2);
		}
	}
	
	public void PreTrav_Right(TreeNode node, ArrayList<Double> vals, double added)
	{
		vals.add(node.val+added);
		
		if(node.right != null)
		{
			PreTrav_Right(node.right,vals,0.4);
		}
		
		if(node.left != null)
		{
			PreTrav_Right(node.left, vals,0.2);
		}
	}

	public boolean isSymmetric(TreeNode root) {
		
		if(root == null)
			return true;
		
		ArrayList<Double> leftArr = new ArrayList<Double>();
		ArrayList<Double> rightArr = new ArrayList<Double>();
		
		PreTrav_Left(root,leftArr, 0.0f );
		PreTrav_Right(root,rightArr, 0.0f);
		
		if(leftArr.size() != rightArr.size())
			return false;
		
		for(int i=0;i<leftArr.size();i++)
		{
			double l = leftArr.get(i);
			double r = rightArr.get(i);
			
			if(l != r)
				return false;
		}
		
		return true;
	}
	
	
	public static void main(String[] args)
	{
		Solution s = new Solution();
		TreeNode root = s.new TreeNode(1);
		
		System.out.println(s.isSymmetric(root));
	}

}