【LeetCode】100. Same tree

---

Their thinking ： 

The structure and values of the tree are the same , That's right. .

1） According to the binary tree, there are left and right parts , So recursively compare the values of each corresponding node in the left part , The values of each corresponding node in the right part are compared , It is correct that they are all equal

        if not p and not q:        # If it's all empty , It's the same thing 
            return True
        elif not p or not q:        # If one is empty FALSE
            return False
        elif p.val != q.val:        # If the corresponding node values are not equal F
            return False
        else :
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
                                    # Cycle the corresponding nodes of the left and right parts 

---

2） Since the structure is required to be the same , Preorder traversal of two numbers , Each node corresponds to , If the values are equal True,

Use a stack to store the nodes of two trees , Store two corresponding nodes each time , Make sure the structure is the same ,

Because the previous sequence traverses around the root , Compare the root node first , In the left part of the comparison , The left part is gone , Compare the right part of the loop

        stack = []        # Storage node data 
        if not p and not q:    # All is empty TRUE
            return True
        elif not p or not q:        # An empty FALSE
            return False
        while p or q or stack:       # When the traversed node and stack are not all empty 
            while p or q:            
                if not p or not q:    # When one of the two nodes traversed is empty 
                    return False
                if p.val != q.val:    # Two corresponding nodes exist but their corresponding values are different F
                    return False     
                stack.append(p)        # The nodes have the same value , After adding to the stack, the preamble traverses the next ,
                stack.append(q)
                p = p.left
                q = q.left
            q = stack.pop()        # Reach the far left rear , Traverse the right child loop of the last node 
            p = stack.pop()
            p = p.right
            q = q.right        # When the last two elements are taken out, the stack is empty , And the two nodes are empty , end 
        return True