Straightforward BFS using Stack to determine symmetric


  • 0
    S

    I just found that nobody post this idea, so I will post the code. Though this takes more space, this is more clear.

        public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root.left);
            q.add(root.right);
            while(!q.isEmpty()){
                int size = q.size();
                Stack<TreeNode> stack = new Stack<TreeNode>();
                for(int i = 0; i < size; i++){
                    TreeNode node1 = q.poll();
                    if(i < size / 2){
                        stack.push(node1);
                    }else{
                        TreeNode node2 = stack.pop();
                        if(node1 == null && node2 == null) continue;
                        if(node1 == null || node2 == null) return false;
                        if(node1.val != node2.val) return false;
                    }
                    if(node1 != null){
                        q.add(node1.left);
                        q.add(node1.right);
                    }
                }
            }
            return true;
        }
    

Log in to reply
 

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