Concise 15 line non-recursive solution. Easy to understand.


  • 1
        public boolean isSymmetric(TreeNode root) {
            Stack<TreeNode> ios = new Stack<>(), ros = new Stack<>();
            TreeNode io = root, ro = root;
            while ((io != null || !ios.isEmpty()) && (ro != null || !ros.isEmpty())) {
                while (io != null && ro != null) {
                    if (io.val != ro.val) return false;
                    ios.push(io); ros.push(ro);
                    io = io.left; ro = ro.right;
                }
                if (io != null || ro != null) return false;
                io = ios.pop(); ro = ros.pop();
                if (io.val != ro.val) return false;
                io = io.right; ro = ro.left;
            }
            return true;
        }
    

    ios = in order stack
    io = in order
    ros = reverse order stack
    ro = reverse order

    The idea here is just to do in order traversal twice at the same time, once in proper order and once in reverse order. If at anytime during the traversal, there is a difference in structure or value, then just return false. If traversal is finished - return true.


Log in to reply
 

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