Python Iterative DFS using stacks with comments

  • 0
    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
            return True

  • 0

    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.