对称的二叉树

[编程题]对称的二叉树

热度指数：478560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的

下面这棵二叉树不对称。

数据范围：节点数满足 $0 \le n \le 1000$ ，节点上的值满足 $|val| \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

备注：

你可以用递归和迭代两种方法解决这个问题

示例1

输入

{1,2,2,3,4,4,3}

输出

true

示例2

输入

{8,6,9,5,7,7,5}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

推荐

Ron

/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
* 左子树的右子树和右子树的左子树相同即可，采用递归
* 非递归也可，采用栈或队列存取各级子树根节点
*/
public class Solution {
	boolean isSymmetrical(TreeNode pRoot)
	{
		if(pRoot == null){
			return true;
		}
		return comRoot(pRoot.left, pRoot.right);
	}
	private boolean comRoot(TreeNode left, TreeNode right) {
		// TODO Auto-generated method stub
		if(left == null) return right==null;
		if(right == null) return false;
		if(left.val != right.val) return false;
		return comRoot(left.right, right.left) && comRoot(left.left, right.right);
	}
}

编辑于 2015-08-18 23:10:28 回复(46)