### 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:
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.

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