Python Iterative DFS using stacks with comments


  • 0
    W
    class Solution(object):
        def isSameTree(self, p, q):
            """
            :type p: TreeNode
            :type q: TreeNode
            :rtype: bool
            """
            # iterative dfs
            stack = [(p,q)]
            while stack:
                p1,q1 = stack.pop()
                # Both are None, skip current iteration and stack will be empty
                # True will be returned
                if not p1 and not q1: continue
                
                # Only one of them is None: apparently not the same
                if (p1 or q1) and None in (p1,q1): return False
                
                # Not same root value, false
                if p1.val!=q1.val: return False
                
                # push back subtrees
                stack.append((p1.left,q1.left))
                stack.append((p1.right,q1.right))
            return True
    

  • 0
    W

    For BFS version, please go here.


Log in to reply
 

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