BST的非递归和递归中序，前序，后序遍历

中序遍历算法思路：

如图所示，总体思路是左节点按层次遍历，而区别在于何时加入到结果集。

1. 首先初始化将root的所有左儿子加入到stack。
2. 开始循环，取出节点，判断其右儿子不为空，因为左儿子已经访问过。
3. 若右子树不为空，跟初始化一样，将右子树的所有左儿子加入到栈中。
4. 用到两个指针node和n，分别指向出栈节点和遍历所有左儿子节点。

若前序遍历，只要把打印语句从出栈时打印移到入栈时打印即可。见L144

应用：

1. BST的关于Iterator的题目Leetcode 173
2. 不需要遍历所有节点而需要遍历某些节点的题目如求某target最接近N个节点。Leetcode 272

中序遍历

Leetcode 094 Binary Tree Inorder Traversal

Python代码：

def iterative_inorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		it = it.left
	while stack:
		node = stack.pop()
		res.append(node.val)
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				n = n.left
	return res

前序遍历

Leetcode 144 Binary Tree Preorder Traversal
只要将出栈节点加入结果换到入栈前加即可，也就是将Line 11换到取Line 7和Line 15

Python代码：

def iterative_preorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		res.append(it.val)
		it = it.left
	while stack:
		node = stack.pop()
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				res.append(n.val)
				n = n.left
	return res

后序遍历

Leetcode 145 Binary Tree Postorder Traversal
跟中序比，需要用一个记数器来记录出现在栈顶的次数，若为2次就加入到结果集，并且不能继续迭代到右节点，因为第一次时候已做了。
由于tuple不可改，所以即使次数为1，也要出栈，更新次数后重新入栈。代码区别在Line 10 - 17.

注意事项：

1. 记得要continue。

Python代码：

def iterative_postorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append((it, 0))  # count for it in the stack top
		it = it.left
	while stack:
		pair = stack.pop()
		node = pair[0]
		occurrence = pair[1] + 1
		if occurrence == 2:
			res.append(node.val)
			continue  # don't iterate on right node again
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

递归写法

DFS
BST的递归前序遍历Leetcode 0144
BST的递归中序遍历Leetcode 0094

Python代码：

def recursive_inorder(self, root: TreeNode) -> List[int]:
	return self.dfs_inorder(root)

def dfs_inorder(self, root):
	if not root:
		return []
	return self.dfs_inorder(root.left) + [root.val] + self.dfs_inorder(root.right)

def recursive_preorder(self, root: TreeNode) -> List[int]:
	return self.recursive_preorder(root)

def recursive_preorder(self, root):
	if not root:
		return []
	return [root.val] + self.recursive_preorder(root.left) + self.recursive_preorder(root.right)

def recursive_postorder(self, root: TreeNode) -> List[int]:
	return self.recursive_postorder(root)

def recursive_postorder(self, root):
	if not root:
		return []
	return self.recursive_postorder(root.left) + self.recursive_postorder(root.right) + [root.val]

Java代码：

protected void iterativeInorder(BinaryNode p) {  
	Stack<BinaryNode> stack = new Stack<BinaryNode>();  
	BinaryNode head = p;
	while(head != null) {
		stack.push(head);
		head = head.left;
	}
	
	BinaryNode node = null;
	while (stack.size() > 0) {  
		node = stack.pop();
		System.out.print(node.data);
		if(node.right != null) {
			BinaryNode n = node.right; 
			while(n != null) {
				stack.push(n);
				n = n.left;
			}
		}
	}  
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(logn)，最差为O(n)。