April
3rd,
2017
Table of Contents
1. 二叉树的遍历
1.1 Inorder Traversal
1.递归算法
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes = []
self.inorder(root ,nodes)
return nodes
def inorder(self, root, nodes):
if not root:
return
self.inorder(root.left, nodes)
nodes.append(root.val)
self.inorder(root.right, nodes)
2.用堆栈实现迭代算法
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes, toVisit = [], []
curNode = root
while curNode or len(toVisit) != 0:
if curNode:
toVisit.append(curNode)
curNode = curNode.left
else:
curNode = toVisit[-1]
toVisit.pop()
nodes.append(curNode.val)
curNode = curNode.right
return nodes
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<Integer>();
LinkedList<TreeNode> toVisit = new LinkedList<TreeNode>();
TreeNode curNode = root;
while(curNode!=null || !toVisit.isEmpty()){
while(curNode!=null){
toVisit.add(curNode);
curNode = curNode.left;
}
curNode = toVisit.removeLast();
nodes.add(curNode.val);
curNode = curNode.right;
}
return nodes;
}
3.Morris遍历
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes, toVisit = [], []
curNode = root
while curNode:
if curNode.left:
predecessor = curNode.left
while predecessor.right and predecessor.right != curNode:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = curNode
curNode = curNode.left
else:
predecessor.right = None
nodes.append(curNode.val)
curNode = curNode.right
else:
nodes.append(curNode.val)
curNode = curNode.right
return nodes
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<Integer>();
LinkedList<TreeNode> toVisit = new LinkedList<TreeNode>();
TreeNode curNode = root;
while(curNode!=null){
if(curNode.left != null){
TreeNode predecessor = curNode.left;
while(predecessor.right != null && predecessor.right != curNode)
predecessor = predecessor.right;
if(predecessor.right == null){
predecessor.right = curNode;
curNode = curNode.left;
} else{
predecessor.right = null;
nodes.add(curNode.val);
curNode = curNode.right;
}
} else{
nodes.add(curNode.val);
curNode = curNode.right;
}
}
return nodes;
}
1.2 Preorder Traversal
1.递归算法
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes = []
self.preorder(root ,nodes)
return nodes
def preorder(self, root, nodes):
if not root:
return
nodes.append(root.val)
self.preorder(root.left, nodes)
self.preorder(root.right, nodes)
2.用堆栈实现迭代算法
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes, toVisit = [], []
curNode = root
while curNode or len(toVisit) != 0:
if curNode:
nodes.append(curNode.val)
toVisit.append(curNode)
curNode = curNode.left
else:
curNode = toVisit.pop()
curNode = curNode.right
return nodes
3.修改Morris遍历
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes, toVisit = [], []
curNode = root
while curNode:
if curNode.left:
predecessor = curNode.left
while predecessor.right and predecessor.right != curNode:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = curNode
nodes.append(curNode.val)
curNode = curNode.left
else:
predecessor.right = None
curNode = curNode.right
else:
nodes.append(curNode.val)
curNode = curNode.right
return nodes
1.3 Postorder Traversal
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
nodes = []
self.postorder(root ,nodes)
return nodes
def postorder(self, root, nodes):
if not root:
return
self.postorder(root.left, nodes)
self.postorder(root.right, nodes)
nodes.append(root.val)
2. BFS
def BFS(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue = []
queue.append(root)
res = []
while len(queue):
curLevel = []
for i in range(len(queue)):
curNode = queue.pop(0)
curLevel.append(curNode.val)
if curNode.left:
queue.append(curNode.left)
if curNode.right:
queue.append(curNode.right)
res.append(curLevel)
return res
public List<List<Integer>> BFS(TreeNode root) {
if(root == null)
return new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> res = new LinkedList<>();
while(!queue.isEmpty()){
List<Integer> curLevel = new LinkedList<>();
for(int i = 0; i < queue.size(); i++){
TreeNode curNode = queue.removeFirst();
curLevel.add(curNode.val);
if(curNode.left != null)
queue.add(curNode.left);
if(curNode.right != null)
queue.add(curNode.right);
}
res.add(curLevel);
}
return res;
}