94. Binary Tree Inorder Traversal

Problem:

Given a binary tree, return the inorder traversal of its nodes' values.

Trivial Recursive way:

class Solution(object):
    def __init__(self):
        self.traversal = []
        
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root:
            self.inorderTraversal(root.left)
            self.traversal.append(root.val)
            self.inorderTraversal(root.right)
        return self.traversal

Iterative way. Using stack store the root, and loop to find the leftmost node, get the node value, and then turn to the node's right side. If null, turn to the previous node, e.g. the top of the stack. If not null, loop again.

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        traversal = []
        stack = [root]
        current = root
        while stack and stack[0]:
            while current and current.left:
                stack.append(current.left)
                current = current.left
            current = stack.pop()
            traversal.append(current.val)
            current = current.right
            if current:
                stack.append(current)
        return traversal

100. Same Tree

Problem:

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

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

Attention: The same traverse not means the same tree.

The same tree means the same root value, the same left subtree and right subtree.

So, recursive answer:

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
           return True 
        elif (not p and q) or (not q and p):
            return False
        elif not p.val == q.val:
            return False
        left = self.isSameTree(p.left, q.left)
        right = self.isSameTree(p.right, q.right)
        return left and right

Simplify, because of None is None is True.

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q