来自Leetcode第101题对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
递归
1 2 3 4 5 6 7 8 9 10 11
| public boolean isSymmetric(TreeNode root) { return isMirror(root, root); }
public boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right); }
|
迭代
来源题解
除了递归的方法外,我们也可以利用队列进行迭代。队列中每两个连续的结点应该是相等的,而且它们的子树互为镜像。最初,队列中包含的是 root 以及 root。该算法的工作原理类似于 BFS,但存在一些关键差异。每次提取两个结点并比较它们的值。然后,将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。
业转载请联系作者获得授权,非商业转载请注明出处。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public boolean isSymmetric(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); q.add(root); q.add(root); while (!q.isEmpty()) { TreeNode t1 = q.poll(); TreeNode t2 = q.poll(); if (t1 == null && t2 == null) continue; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; q.add(t1.left); q.add(t2.right); q.add(t1.right); q.add(t2.left); } return true; }
|
栈
按自己思路写了一个,用栈的结构,效率低了好多。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public boolean isSymmetric(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); stack.push(root); stack.push(root); while (!stack.isEmpty()) { TreeNode t1 = stack.pop(); TreeNode t2 = stack.pop(); if (t1 == null && t2 == null) continue; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; stack.push(t1.left); stack.push(t2.right); stack.push(t1.right); stack.push(t2.left); } return true; }
|