[剑指offer]面试题第[28]题[Leedcode][JAVA][第101题][对称二叉树][队列][递归]

【问题描述】[简单]

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \3 4 4 3

【解答思路】

1. 递归

时间复杂度：O(N) 空间复杂度：O(1)

public boolean isSymmetric(TreeNode root) {if (root == null) return true;return isMirror(root.left, root.right);}public boolean isMirror(TreeNode node1, TreeNode node2){if (node1 == null && node2 == null) return true;if (node1 == null || node2 == null) return false;if (node1.val != node2.val) return false;return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);}

2. 队列

迭代解法，层次遍历，调整入队顺序

时间复杂度：O(N) 空间复杂度：O(N)

public boolean isSymmetric(TreeNode root) {if (root == null || (root.left == null && root.right == null)) return true;Queue<TreeNode> queue = new LinkedList<>();queue.add(root.left);queue.add(root.right);while (!queue.isEmpty()){TreeNode left = queue.poll();TreeNode right = queue.poll();if (left == null && right == null) continue;if (left == null || right == null) return false;if (left.val != right.val) return false;queue.add(left.left);queue.add(right.right);queue.add(left.right);queue.add(right.left);}return true;}

【总结】

1. 二叉树 递归思路最佳

2.整体思路把控 不要太局部

转载链接：https://leetcode-/problems/symmetric-tree/solution/java-di-gui-yu-die-dai-by-kelly/

参考链接：https://leetcode-/problems/symmetric-tree/solution/hua-jie-suan-fa-101-dui-cheng-er-cha-shu-by-guanpe/

参考链接：https://leetcode-/problems/symmetric-tree/solution/di-gui-die-dai-bi-xu-miao-dong-by-sweetiee/