A Iterative method using preorder traversal


  • 0
    A

    set two pointer to traverse the tree,one's order is left-middle-right,another is right-middle-left

    public:
        bool isSymmetric(TreeNode* root) {
            if(root==NULL)
                return true;
            
            TreeNode* firstP=root;
            TreeNode* secondP=root;
            stack<TreeNode*> firstStack;
            stack<TreeNode*> secondStack;
            
            while((firstP||!firstStack.empty())&&(secondP||!secondStack.empty()))
            {
                while(firstP&&secondP)
                {
                    if(firstP->val!=secondP->val)
                        return false;
                    firstStack.push(firstP);
                    firstP=firstP->left;
                    
                    secondStack.push(secondP);
                    secondP=secondP->right;
                }
                if(firstP!=secondP)
                    return false;
                TreeNode* tmpFirstP=firstStack.top();
                firstP=tmpFirstP->right;
                firstStack.pop();
                TreeNode* tmpSecondP=secondStack.top();
                secondP=tmpSecondP->left;
                secondStack.pop();
            }
            if(firstP!=secondP)
                return false;
            return true;
        }
    };```

Log in to reply
 

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