首页 > itarticle > [leetcode] lc101

[leetcode] lc101

admin 11月 14, 2020 0

Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
 
    1
   / 
  2   2
 /  / 
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
 
  1
 / 
2   2
    
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

> Solve problem here

Test Cases

  • null root
  • one root
  • complete + symmetric binary tree
  • non-complete + symmetric binary tree

Thoughts

Create a helper() method to check if two symmetric nodes share the same value. It takes in TreeNode n1 and TreeNode n2 as two arguments and return values based on conditions. Note, root node is handled sperately.

  • Return true if n1 == null && n2 == null
  • Return false if n1 == null || n2 == null
  • Return false if n1.val != n2.val
  • Return helper(n1.left, n2.right) && helper(n1.right, n2.left)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 


// time: 
// space:
class  {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return helper(root.left, root.right);
    }
    
    public boolean helper(TreeNode n1, TreeNode n2) {
        if (n1 == null && n2 == null) return true;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        return helper(n1.left, n2.right) && helper(n1.right, n2.left);
    }
}

Solution above use recursive dfs, the problem can also be solved by iterative dfs with a stack.

Thoughts (iterative dfs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
// iterative dfs
public boolean isSymmetric2(TreeNode root) {
    if (root == null) return true;

    // Deque<TreeNode> stack = new ArrayDeque<>(); ArrayDeque did not support NULL? hence use Stack -> new Stack?
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root.left);
    stack.add(root.right);
    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.right);
        stack.push(t2.left);
        stack.push(t1.left);
        stack.push(t2.right);
    }
    return true;
}

Thoughts (iterative bfs)

iterative BFS approah ues queue data structure to process node level by level. This might have a better performance, since it goes level by level, catch unmatch node pair sooner and return false immediately without going too deep of the tree (like DFS approach).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
// iterative bfs
public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.remove();
        TreeNode t2 = q.remove();
        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;
}

[Reference]

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能