leetcode101_对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

思路：

1.拿到此题，就想到递归，思路就是根节点的左右子树是否对称

贴代码：代码上有详细注释

    // 递归的解答
	public boolean isSymmetric(TreeNode root) {
		if (root == null) {
			return true;
		}
		return getResult(root.left, root.right);
	}

	private static boolean getResult(TreeNode left, TreeNode right) {
		if (left == null && right == null) { // 都为空
			return true;
		}
		if (left == null || right == null) { // 只有一个为空
			return false;
		}
		if (left.val != right.val) { // 左右孩子值不相等
			return false;
		}

		return getResult(left.left, right.right) && getResult(left.right, right.left);
	}

2. 非递归 自己用两个栈实现 每个根节点左边的孩子 左孩子入栈s1 对每个根节点右边的孩子 右孩子入栈s2 根节点两个栈都入

public boolean isSymmetric2(TreeNode root) {
		if (root == null) {
			return true;
		}
		Stack<TreeNode> stack1 = new Stack<>();     //放左边的孩子
		Stack<TreeNode> stack2 = new Stack<>();     //放右边的孩子
		TreeNode leftNode = root;                   //根节点两个都放才保证两个栈大小相等
		TreeNode rightNode = root;
		while (true) {
			if (leftNode != null && rightNode != null) {       //都不为空入栈
                  stack1.push(leftNode);
                  stack2.push(rightNode);
                  leftNode=leftNode.left;      //到左孩子
                  rightNode=rightNode.right;   //到右孩子
			} else if (leftNode == null && rightNode == null) { //都为空 继续判断其他条件  
				if (stack1.isEmpty()&&stack2.isEmpty())  //两个栈都空了
					break;
				leftNode=stack1.pop();      //弹出（左边）栈1元素
				rightNode=stack2.pop();     //弹出（右边）栈2元素
				if (leftNode.val!=rightNode.val) return false;				 
					
				leftNode=leftNode.right;   //到右孩子
				rightNode=rightNode.left;  //到左孩子				
			}else {//有一个为空的情况  直接返回false
				return false;
			}
		}        
		//能执行到这里说明前面没有false的情况
		return true;
	}