Slim Java solution


  • 30
    A

    The idea is:

    1. level traversal.

    2. push nodes onto stack, every 2 consecutive is a pair, and should either be both null or have equal value.
      repeat until stack is empty.

      public boolean isSymmetric(TreeNode root) {
      if (root == null)
      return true;
      Stack<TreeNode> stack = new Stack<TreeNode>();
      stack.push(root.left);
      stack.push(root.right);
      while (!stack.isEmpty()) {
      TreeNode node1 = stack.pop();
      TreeNode node2 = stack.pop();
      if (node1 == null && node2 == null)
      continue;
      if (node1 == null || node2 == null)
      return false;
      if (node1.val != node2.val)
      return false;
      stack.push(node1.left);
      stack.push(node2.right);
      stack.push(node1.right);
      stack.push(node2.left);
      }
      return true;
      }


  • 0
    S

    is it possible to implement the same idea with queue?


  • 0
    A

    Yes.
    /*

    • Iterative approach
      */
      public boolean isSymmetric(TreeNode root) {
      if (root == null) return true;
      Queue<TreeNode> queue = new LinkedList<TreeNode>();
      queue.add(root.left);
      queue.add(root.right);
      while (!queue.isEmpty()) {
      TreeNode n1 = queue.poll();
      TreeNode n2 = queue.poll();
      if (n1 == null && n2 == null)
      continue;
      else if (n1 != null && n2!= null && n1.val == n2.val) {
      queue.add(n1.left);
      queue.add(n2.right);
      queue.add(n1.right);
      queue.add(n2.left);
      } else
      return false;
      }
      return true;
      }

  • 3
    T

    this isn't level traversal. It is depth first search


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.