LC 100 Same tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Two tree are the same if

  1. Both root nodes are either both empty of both valid
  2. The left subtree of p is the same as the left sub tree of q
  3. The right subtree of p is the same as the right sub tree of q

So we can write a recursive code to check the above three conditions

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p != NULL and q == NULL or(p == NULL and q != NULL))return false;
        return (p->val == q->val && isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right));
    }

ITerative

DFS

To use DFS, we want to first go as deep as possible, so we use a stack to enforce FILO policy so we will always go deep with the current node and only explore other branch when the current branch hit the bottom (null on both left and right children)

    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        s.push(p);
        s.push(q);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode != NULL) return false;
            if(leftNode != NULL && rightNode == NULL) return false;
            if(leftNode != NULL && rightNode != NULL){
                if(leftNode -> val == rightNode -> val){
                    s.push(leftNode -> left);
                    s.push(rightNode -> left);
                    s.push(leftNode -> right);
                    s.push(rightNode -> right);
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax