LeetCode-Symmetric Tree

这题是判断一个二叉树是否对称，如第一棵树。

一开始我的想法很复杂，先把树序列化到数组中，再根据下标计算对称的位置进行判断。

后来发现，假设上面的第二层两个结点为p和q,判断p的左孩子跟q的右孩子是否相等，p的右孩子跟q的左孩子是否相等即可。

/**思路是层次遍历，每次两个结点出队，为p和q,若满足p.left=q.right且p.right=q.left,则入队,直到队列为空。
 * @author admin
 *
 */
public class SymmetricTree {

	public static boolean isSymmetric(TreeNode root) {
		TreeNode[] queue=new TreeNode[256];//这个最好用ArrayList代替
		int head=0;
		int tail=0;
		if(root==null) {//如果根为空
			return true;
		} else if(root.leftChild==null&&root.rightChild==null){//如果左孩子和右孩子都为空
			return true;
		} else if(root.leftChild!=null&&root.rightChild!=null&&root.leftChild.val==root.rightChild.val) {//若两者都不为空且值相等
			queue[tail++]=root.leftChild;//左孩子入队
			queue[tail++]=root.rightChild;//右孩子入队
		} else {//若两者其中一个为空
			return false;
		}
		boolean flag=true;
		while(head!=tail&&flag) {//当队列不为空且flag==true时
			TreeNode node1=queue[head++];//出队
			TreeNode node2=queue[head++];
			//判断其node1的左孩子和node2的右孩子是否相等
			if(node1.leftChild!=null||node2.rightChild!=null) {
				if(node1.leftChild!=null&&node2.rightChild!=null){
					if(node1.leftChild.val==node2.rightChild.val) {
						queue[tail++]=node1.leftChild;
						queue[tail++]=node2.rightChild;
					} else {
						return false;
					}
				} else {
					return false;
				}
					
				
			}
			//判断其node1的右孩子和node2的左孩子是否相等
			if(node1.rightChild!=null||node2.leftChild!=null) {
			if(node1.rightChild!=null&&node2.leftChild!=null){
				if(node1.rightChild.val==node2.leftChild.val) {
					queue[tail++]=node1.rightChild;
					queue[tail++]=node2.leftChild;
				} else {
					flag=false;
				}
			}
			 else {
					return false;
				}
		 }
		}
		return flag;
    }
}

但看了discussion以后发现，可以用递归或者栈来实现。

Use two pointers (p, q), traverse the tree simultaneously, p goes in-order while q goes reversed in-order, compare along the way. It can be done with pre-order and reversed pre-order or post-order and reversed post-order as well.

public boolean isSymmetric(TreeNode root) {
    return traverse(root, root);
}

private boolean traverse(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;

    if (!traverse(p.left, q.right)) 
        return false;
    if (p.val != q.val) return false;
    return traverse(p.right, q.left);
}

于是我想出了下面的解法。

public static boolean isSymmetricTree(TreeNode root) {
		return traverse(root,root);
	}
	public static boolean traverse(TreeNode p,TreeNode q) {
		//如果两者同时为空，则为true
			if(p==null&&q==null) {
				return true;
			}
			//如果其中一个不为空，则为false
			if(p==null||q==null) {
				return false;
			}
			//判断值是否相等
			return p.val==q.val&&traverse(p.left,q.right)&&traverse(p.right,q.left);
	}

其实树的很多问题都可以使用递归来解决，先找出一定的规律，再用递归来解决就很容易了。

例如判断两棵树是否相等。

 public static boolean isSameTree(TreeNode p, TreeNode q) {
	        return traverse(p, q);
	    }
	 public static boolean traverse(TreeNode p,TreeNode q) {
			if(p==null&&q==null) {
				return true;
			}
			if(p==null||q==null) {
				return false;
			}
			return p.val==q.val&&traverse(p.right,q.right)&&traverse(p.left,q.left);
	}