Share my non-recursive solution in C++.


  • 1
    M
       class Solution {
    public:
        typedef pair<TreeNode*, TreeNode*> pr_t;
        bool isSameTree(TreeNode *p, TreeNode *q) { // A stack is used to do non-recursive preoder.
                                                    // Do comparing when the binary tree is iterated.
            bool is_same = true;
            stack<pr_t> s;
            pr_t tmp_pair;
            
            if (p == 0 && q == 0) {
                is_same = true;
            } else {
                s.push(make_pair(p, q));   
            }
            
            while (!s.empty()) {
                tmp_pair = s.top();
                s.pop();
                TreeNode *first     = tmp_pair.first;
                TreeNode *second    = tmp_pair.second;
                if ((first && !second) || (!first && second)) {
                    is_same = false;
                    break;
                }
                
                if (!first && !second) {
                    continue;
                }
                
                if (first->val != second->val) {
                    is_same = false;
                    break;
                }
                
                s.push(make_pair(first->right, second->right));
                s.push(make_pair(first->left, second->left));
            }   
            return is_same;
        }
    };

Log in to reply
 

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