java, easy understanding iterator solution using stack


  • 0

    The idea is the same as traverse a tree using stack, but this time, just traverse two trees at the same time.

    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            if(root == null || root.left == null && root.right == null) {
                return true;
            }
            if(root.left == null || root.right == null) {
                return false;
            }
            LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
            TreeNode node1 = root.left;
            TreeNode node2 = root.right;
            while((node1 != null && node2 != null) || !stack.isEmpty()) {
                if(node1 == null && node2 != null || node1 != null && node2 == null) {
                    return false;
                }
                if(node1 != null && node2 != null) {
                    if(node1.val != node2.val) {
                        return false;
                    }else {
                        stack.push(node1);
                        stack.push(node2);
                    }
                    node1 = node1.left;
                    node2 = node2.right;
                }else {
                    TreeNode t2 = stack.pop();
                    TreeNode t1 = stack.pop();
                    node1 = t1.right;
                    node2 = t2.left;
                }
            }
            return node1 == null && node2 == null ? true : false;
        }
    }

Log in to reply
 

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