A tree is a frequently-used data structure to simulate a hierarchical tree structure.
Each node of the tree will have
From graph view, a tree can also be defined as a directed acyclic graph which has N nodes and N-1 edges.
A Binary Tree is a tree data structure in which each node has at most two children:
Pre-order Traversal: root -> left subtree -> right subtree.
In-order traversal:: left subtree -> root -> right subtree.
Post-order traversal: left subtree -> right subtree -> root.
when you delete nodes in a tree, deletion process will be in post-order. That is to say, when you delete a node, you will delete its left child and its right child before you delete the node itself.
post-order is widely use in mathematical expression. It is easier to write a program to parse a post-order expression.
Given a binary tree, return the preorder traversal of its nodes' values.
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def preorderTraversal(self, root):
if root is None:
return []
stack = [root]
result = []
while len(stack)>0: # use while to do iteration
cur_node = stack.pop()
result.append(cur_node.val) # pop out the node of the root and append its value
if cur_node.right is not None:
stack.append(cur_node.right)
if cur_node.left is not None:
stack.append(cur_node.left)
return result
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
stack, result = [root], []
while stack:
if root.left:
stack.append(root.left)
root = root.left
else:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
root = node.right
return result
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
class Solution(object):
def postorderTraversal(self, root):
if root is None:
return []
stack,result = [],[]
cur_node = root
# stack all the nodes into stack in the order: right->root->left
while True:
while root:
if root.right:
stack.append(root.right)
stack.append(root)
root = root.left
root = stack.pop()
if root.right and stack and stack[-1] == root.right:
stack.pop()
stack.append(root)
root = root.right
else:
result.append(root.val)
root = None
if len(stack)<=0:
break
return result
Level-order traversal is to traverse the tree level by level.
When we do breadth-first search in a tree, the order of the nodes we visited is in level order.
Given a binary tree, return the level order traversal of its nodes' values.
(ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue = [(root, 0)]
levelMap = {}
while queue:
node, level = queue.pop(0)
if node.left:
queue.append((node.left, level+1))
if node.right:
queue.append((node.right, level+1))
if level in levelMap:
levelMap[level].append(node.val)
else:
levelMap[level] = [node.val]
result = []
for key, value in levelMap.iteritems():
result.append(value)
return result
class Node(object):
# create a tree using nodes
def __init__(self,data):
self.right = None
self.left = None
self.val = data
def insert(self,data):
if self.val:
if data < self.val:
if self.left is None:
self.left = Node(data) # attention Node()
else:
self.left.insert(data)
if data > self.val:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.val = data
def PrintTree(self):
if self.left:
self.left.PrintTree() # left nodes
print(self.val) # root node
if self.right:
self.right.PrintTree() # right nodes
#root -> left subtree -> right subtree
def preorderTraversal(self):
root = self
if root is None:
return []
stack = [root]
result = []
while len(stack)>0: # use while to do iteration
cur_node = stack.pop()
result.append(cur_node.val) # pop out the node of the root and append its value
if cur_node.right is not None:
stack.append(cur_node.right)
if cur_node.left is not None:
stack.append(cur_node.left)
return result
# left subtree -> root -> right subtree
def inorderTraversal(self):
"""
:type root: TreeNode
:rtype: List[int]
"""
root = self
if not root:
return []
stack, result = [root], []
while stack:
if root.left:
stack.append(root.left)
root = root.left
else:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
root = node.right
return result
# left subtree -> right subtree -> root
def postorderTraversal(self):
root = self
if root is None:
return []
stack,result = [],[]
cur_node = root
# stack all the nodes into stack in the order: right->root->left
while True:
#
while root:
if root.right:
stack.append(root.right)
stack.append(root)
root = root.left
root = stack.pop()
if root.right and stack and stack[-1] == root.right:
stack.pop()
stack.append(root)
root = root.right
else:
result.append(root.val)
root = None
if len(stack)<=0:
break
return result
def postorderTraversal2(self):
root = self
cur_node = root
stack = []
result = []
while stack or cur_node:
if cur_node:
stack.append(cur_node)
result.append(cur_node.val)
cur_node = cur_node.right
else: # if cur_node without right node, pop out stack
cur_node = stack.pop()
cur_node = cur_node.left
return result[::-1]
def levelOrder(self):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
root = self
if not root:
return []
queue = [(root, 0)]
levelMap = {}
while queue:
node, level = queue.pop(0)
if node.left:
queue.append((node.left, level+1))
if node.right:
queue.append((node.right, level+1))
if level in levelMap:
levelMap[level].append(node.val)
else:
levelMap[level] = [node.val]
result = []
for key, value in levelMap.items():
result.append(value)
return result
root = Node(3) # creat the root node
# add other nodes
# 3
# \
# 9
# / \
# 7 20
# /
# 15
root.insert(9)
root.insert(20)
root.insert(15)
root.insert(7)
root.PrintTree()
root.levelOrder()
root.preorderTraversal()
root.inorderTraversal()
root.postorderTraversal()
root.postorderTraversal2()
Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
For example,
Given the tree:
4
/ \
2 7
/ \
1 3
And the value to search: 2 You should return this subtree:
2
/ \
1 3
In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.
root = Node(4) # creat the root node
root.insert(2)
root.insert(7)
root.insert(1)
root.insert(3)
root.levelOrder()
class Solution(object):
def searchBST(self, root, val):
if not root:
return None
if root.val == val:
return root
elif root.val > val:
return self.searchBST(root.left,val)
else:
return self.searchBST(root.right,val)
search = Solution()
subtree= search.searchBST(root,2)
subtree.levelOrder()
print(search.searchBST(root,5))
A binary tree is univalued if every node in the tree has the same value.
Return true if and only if the given tree is univalued.
Example 1:
Input: [1,1,1,1,1,null,1] Output: true Example 2:
Input: [2,2,2,5,2] Output: false
Note:
The number of nodes in the given tree will be in the range [1, 100]. Each node's value will be an integer in the range [0, 99].
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# method 1
def isUnivalTree(self, root: TreeNode) -> bool:
all_values=[]
def add_values(root):
if root:
all_values.append(root.val)
add_values(root.left)
add_values(root.right)
if not root:
return True
add_values(root)
return len(set(all_values))==1
# method 2
def isUnivalTree2(self, root: TreeNode) -> bool:
if root:
if root.left and not root.right:
if root.val == root.left.val:
return self.isUnivalTree(root.left)
else:
return False
if root.right and not root.left:
if root.val == root.right.val:
return self.isUnivalTree(root.right)
else:
return False
if root.left and root.right:
if root.left.val == root.right.val:
return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)
else:
return False
return True
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 44 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note: Bonus points if you could solve it both recursively and iteratively.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.check_leftright(root.left,root.right)
def check_leftright(self, node1, node2):
if not node1 and not node2:
return True
elif node1 and node2 and node1.val == node2.val:
return self.check_leftright(node1.left,node2.right) and self.check_leftright(node1.right,node2.left)
else:
return False