Given a binary tree, check whether it is mirror-symmetrical.
For example, the binary tree [1,2,2,3,4,4,3] is symmetrical.
1
/ \
2 2
/ \ / \
3 4 4 3
But the following (1,2,2,null,3,null ,3] is not mirror symmetry:
1
/ \
2 2
\ \
3 3
Description:
If You can use recursive and iterative methods to solve this problem, which will add points.
Source: LeetCode
Link: https://leetcode-cn.com/problems/symmetric-tree
The copyright belongs to LeetCode. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.
Use the non-recursive algorithm of pre-order traversal and the non-recursive algorithm of reverse post-order traversal to traverse and compare. However, the time complexity ranking is not high.
1 public < span style="color: #0000ff;">class Solution {
2
3 public boolean isSymmetric(TreeNode root) {
4 if (root == null) return true;
5 // The non-recursive algorithm of pre-order traversal and the non-recursive algorithm of post-order traversal
6 Stackpre = new Stack<>();
7 Stackpost = new Stack< >();
8 TreeNode p = root, q = root;
9
10 do {
11 for (TreeNode i = p, j = q; i != null; i = i.left, j = j.right) {
12 // Visit node
13 try {
14 if (i.val != j.val)
15 return false;
16} catch (NullPointerException e) {
17 return false;
18 }
19 pre.push(i);
20 post.push(j);
21 }
22
23 p = pre.pop().right;
24 q = post.pop().left;
25} while (p != null || !pre.empty());
26 return true;
27 }
28
29 public static void main(String[] args) {
30 //1, 2, 2, 3, 4, 4, 3
31 //1,2,2,null,3,null,3
32 //1,2,3,null,4,5,null
33 TreeNode p = _94.create(new Object[]{1 ,2,2,null,3,null,3});
34 boolean symmetric = new Solution().isSymmetric(p);
35 System.out.println("\nsymmetric = "+ symmetric );
36 }
37 }
1 public class Solution {
2
3 public boolean isSymmetric(TreeNode root) {
4 if (root == null) return true;
5 // The non-recursive algorithm of pre-order traversal and the non-recursive algorithm of post-order traversal
6 Stackpre = new Stack<>();
7 Stackpost = new Stack< >();
8 TreeNode p = root, q = root;
9
10 do {
11 for (TreeNode i = p, j = q; i != null; i = i.left, j = j.right) {
12 // Visit node
13 try {
14 if (i.val != j.val)
15 return false;
16} catch (NullPointerException e) {
17 return false;
18 }
19 pre.push(i);
20 post.push(j);
21 }
22
23 p = pre.pop().right;
24 q = post.pop().left;
25} while (p != null || !pre.empty());
26 return true;
27 }
28
29 public static void main(String[] args) {
30 //1, 2, 2, 3, 4, 4, 3
31 //1,2,2,null,3,null,3
32 //1,2,3,null,4,5,null
33 TreeNode p = _94.create(new Object[]{1 ,2,2,null,3,null,3});
34 boolean symmetric = new Solution().isSymmetric(p);
35 System.out.println("\nsymmetric = "+ symmetric );
36 }
37 }