本文共 2230 字,大约阅读时间需要 7 分钟。
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
进阶:
阅读完题目,脑子里先是想到了栈这种数据结构。
栈的一个特性:先进后出、后进先出。
根据这个特性,很容易地搞定递归实现。
但是迭代地话,用队列更容易理解。
队列的一个特性:先进先出,后进后出。
这题比较容易,直接看代码和注释即可。
class Solution { public boolean isSymmetric(TreeNode root) { // 两树都为null,肯定对称 if (root == null) { return true; } // 比较 左子树root.left 与 右子树root.right 这两棵子树是否对称 return compareTree(root.left, root.right); } /* 递归实现 */ private boolean compareTree(TreeNode node1, TreeNode node2) { // 首先比较 node1 与 node2 这两个节点的值是否相等 // 两节点均同时为null时 if (node1 == null && node2 == null) { return true; } // 最多一个节点为null时,当然还得考虑“值不空但不同”的情况 if (node1 == null || node2 == null || node1.val != node2.val) { // TreeNode.val返回的是该节点的值 return false; } // 再递归比较 node1 的左子树与 node2 的右子树是否对称,node1 的右子树与 node2 的左子树是否对称 return compareTree(node1.left, node2.right) && compareTree(node1.right, node2.left); }}
class Solution { public boolean isSymmetric(TreeNode root) { // 两树都为null,肯定对称 if (root == null) { return true; } Queuequeue = new LinkedList<>(); queue.add(root.left); queue.add(root.right); while (!queue.isEmpty()) { // 每次出队两个节点 node1 和 node2 TreeNode node1 = queue.poll(); TreeNode node2 = queue.poll(); // 首先比较 node1 与 node2 这两个节点的值是否相等 if (node1 == null && node2 == null) { continue; } // 最多一个节点为null时,当然还得考虑“值不空但不同”的情况 if (node1 == null || node2 == null || node1.val != node2.val) { // TreeNode.val返回的是该节点的值 return false; } // 再将 node1 的左节点与 node2 的右节点一起入队(以便两节点一起出队,进行比较) queue.add(node1.left); queue.add(node2.right); // 再将 node1 的右节点与 node2 的左节点一起入队(以便两节点一起出队,进行比较) queue.add(node1.right); queue.add(node2.left); } return true; }}
无论是递归,还是迭代,
时间复杂度均为:O(n)
空间复杂度均为:O(n)
转载地址:http://fmatf.baihongyu.com/