二叉树类算法题目
二叉树题目思想总结
二叉树解题的方法主要分两种，一种是递归，一种是迭代。
当题目有较清晰的子结构时可以选择递归。递归调用系统栈，可能占较大空间，在优化成迭代方法时我们会手动维护一个栈/队列。
1. 二叉树的遍历
二叉树的遍历是一类较经典的题目，现简单总结其思路如下。
对于二叉树遍历的理论提炼请见我的另一篇博客，对于广度/深度搜索的知识详见我的另另一篇博客。本博客主要侧重代码实现。
写在前边
参考Leetcode官解的一张图：
前、中、后序遍历的核心思想均是深度优先搜索，基于栈实现；层序遍历的核心思想是广度优先搜索，基于队列实现。
前序遍历
二叉树的前序遍历顺序为根->左->右。
递归
在递归时从左至右遍历节点。
def dfs(root):
if root:
print(root) # other op
dfs(root.left)
dfs(root.right)
注意边界条件(叶节点/空节点)的判断和扩展节点的顺序(从左到右)。
迭代
dfs是后入先出结构，故采用栈实现。首先将初始节点压入栈，每个节点出栈时将其标记为已读并将其子节点由右至左压入栈，出栈过程即为输出过程。
def dfs(root):
stack = [root]
while(stack):
node = stack.pop()
print(node) # other op
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
还有一种近似于模板的写法，其思路为：先将根节点和所有的左孩子入栈并输出，每次当前节点为空时，弹出栈顶元素并访问其右孩子，循环操作。
def dfs(root):
cur = root
stack = []
while cur or stack:
if cur:
print(cur) # other op
stack.append(cur)
cur = cur.left
else:
tmp = stack.pop()
cur = tmp.right
中序遍历
二叉树的中序遍历顺序为左->根->右。
递归
def dfs(root):
if root:
dfs(root.left)
print(root) # other op
dfs(root.right)
迭代
参考上述模板，这次是在出栈时输出：
def dfs(root):
cur = root
stack = []
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
tmp = stack.pop()
print(tmp) # other op
cur = tmp.right
后续遍历
二叉树的中序遍历顺序为左->右->根。
递归
def dfs(root):
if root:
dfs(root.left)
dfs(root.right)
print(root) # other op
迭代
后序遍历的迭代方法较为复杂，一种方法是将前序遍历的根-左-右代码稍加调整，变成根-右-左形式，再倒序输出结果，此方法不够劲，此处不加赘述。此处介绍一种基于辅助数组记忆已遍历节点的方法：
def bfs(root):
stack = [(0, root)] # untraversed
while stack:
flag, node = stack.pop()
if not node:
continue
if flag:
print(node)
else:
stack.append((1, node))
stack.append((0, node.right))
stack.append((0, node.left))
层序遍历
层序遍历与广度优先搜索方法类似，逐层遍历，用队列进行实现。由于不存在明显的子结构，故放弃递归思路，用迭代法进行实现。
迭代
迭代的核心思路是将初始节点压入队列后，在出队列输出该节点的同时，从左到右遍历并将其子节点压入队列。
def bfs(root):
queen = [root]
while queen:
node = queen.pop(0)
print(node) # other op
if node.left:
queen.append(node.left)
if node.right:
queen.append(node.right)
部分代码参考博客，在此致谢。
2. 二叉树祖先问题
3. 二叉树高度问题
4. 二叉树路径问题
5. 二叉树结构问题
6. 二叉树
TODO
前序遍历：莫里斯遍历