#二叉树的遍历
##非递归 Morris
思想是利用prev节点(左孩子的最右子节点)的右节点保存当前node节点，从而保证能安全访问左节点并且能退回当前节点。
对于前序遍历和中序遍历，均是按照左、中、右的访问方式，遍历整个树结构，分别用cur和prev表示当前节点和上一个节点。prev节点是为了防止左节点已经被访问过。中序遍历算法流程为：
- 如果cur左节点存在，则根据prev指针的右孩子节点情况考虑遍历左子树还是右子树。
1.1. 如果prev的右孩子为空，则说明左子树还未访问。
此时访问左子树，并设置prev的右指针为当前节点。
1.2. 如果prev的右孩子不为空，则说明左子树已经访问完成，访问右子树。
此时复原指针，重新设置prev的右指针为空，并将当前指针设置为右孩子即可- 如果cur左节点不存在，访问该节点，并设置节点指针为右孩子即可。
对于后续遍历，由于其需要左、右、中的遍历方式，其实现和前、中序略有不同，当左子树访问完，回到父亲节点时，不能立即访问父亲节点，而应访问右子树，待访问完右子树后，才能回来访问父亲节点。这里主要需要两个trick，
需要一个dump指针，将它的左孩子设为root，右孩子为空。
这是为了防止遍历完右子树后无法回到父亲节点的情形。当访问完左子树回到父亲节点时，应逆序输出从当前节点的左节点到prev节点路径上的所有节点。这实际上是一条右子树的路径。
由于每次回到父亲节点时，都不会访问父亲节点，而直接访问了右子树。这使得从父亲节点的左子树开始到prev节点路径上的所有节点的右子树都没有访问，从而此时需要对所有节点进行逆序访问。
由于路径是一条右子树的路径，逆序访问时，可采用如下办法：1
reverse(from ,to) #将路径进行一次颠倒 visit(from, to) #由于路径已经逆序了，可直接访问 reverse(from, to) #将路径回到初试状态 def reverse(from, to): if from == to: return x = from while true: y, z = x.right, y.right y.right, x.right = x, z if x == to: break def visitReverse(from, to): reverse(from, to) node = to while true: visit(node) if node == from: break node = node.right reverse(from, to) def postOrder(root): cur = TreeNode(-1) cur.left = root while cur: if not cur.left: cur = cur.right else: prev = cur.left while prev.right and prev.right != cur: prev = prev.right if not prev.right: prev.right = cur cur = cur.left else: prev.right = None visitReverse(cur.left, prev) cur = cur.right
##非递归 (栈)
###中序遍历
思想为模拟遍历过程，用栈保存待访问的路径。每次优先访问左节点，直到左节点不存在，此时从栈中取出对首元素，访问，并接着设置访问右节点。1
init Stack s
while node and not s.empty():
if node:
s.push(node)
node = node.left
else:
node = s.pop()
visit(node)
node = node.right
###前序遍历 & 后续遍历
思想为用栈保存待访问元素，并按照一定顺序存入左右子树，保证访问顺序。
对于先序遍历，按照先右后左的顺序放入栈中，从而保证访问的顺序是中、左、右。
对于后续遍历，按照先右后左的顺序放入栈中，从而保证访问的顺序是中、右、左。接着再反向输出结果即可。1
init Stack s and Array res
s.push(node)
while !s.empty():
node = s.pop()
res.append(node.val)
if node.left:
s.push(node.left)
if node.right:
s.push(node.right)
revrse(res)
##迭代器
思想为用栈保存待访问元素，每次执行next时，从栈首取出元素，并按照一定规则压入节点到栈中
###后续遍历
思想为：初始时按照先左后右的顺序，将从当前节点到最深层节点的所有孩子压入栈中
1 | while node: s.push(node) node = node.left ? node.left : node.right |
- 每次从栈中取出对首并访问后，检查cur节点与父亲节点的关系
1.1. 如果cur节点是父亲节点的左孩子，则需首先访问右子树。此时将cur置为右孩子，像初始化时，将深层路径上的孩子都压入栈中
1.2. 否则说明左右子树都已经访问，什么事也不用做1
cur = pop(); if (!s.empty() && s.top()->left == cur): node = s.top()->right; while(node != NULL): s.push(node) node = node.left ? node.left : node.right return cur.val;
###中序遍历的Prev、Next迭代器
找node中序遍历的next节点方法为：
当node存在右指针时，next即为右孩子的最左节点
否则找到其父亲节点p。
当node是父亲节点左指针时，则父亲节点是next节点
否则表明父亲节点已经访问，继续向上回溯。此时设置node = p, 继续执行21
def init(root, val):
node = root
while node:
st.append(node)
if node.val < val:
node = node.right
else if node.val > val:
node = node.left
else:
break
def next():
ret = st.pop()
if ret.right:
node = ret.right
while node:
st.append(node)
node = node.left
else:
while st:
parent = st[-1]
if parent.left == node:
break
node = parent
st.pop_left()
return ret
方法：实现Prev和Next迭代器，分别取k个值，找到最接近的k个。
题目：给定一颗二叉搜索树，返回和为target的所有组合
方法：实现中序和逆序迭代器，根据两个头结点sum的大小，移动迭代器。
#多叉树的遍历
##前序遍历
使用队列即可1
que = deque(root)
while que:
node = que.popleft()
result.append(node.val)
for child in node.children:
que.append(child)
##后续遍历
思想为用栈保存所有待访问元素，用pre保存上次访问的元素。
在初始时，压入所有最左子树
从栈中取出栈首元素，需检查其是否存在孩子节点
如果不存在，则访问该元素即可
否则，需检查pre是当前元素的第几个孩子。
如果为最后一个孩子，访问当前元素即可
否则需要选取下一个孩子，并将该孩子的所有最左孩子压入栈中1
node = self.st[-1] # get top
if node.children:
next_idx = -1
for i, child in enumerate(node.children):
if child == self.pre:
next_idx = i
break
if next_idx+1 != len(node.children):
child = node.children[next_idx+1]
while child:
self.st.append(child)
if not child.children:
break
else:
child = child.children[0]
self.pre = self.st.pop()
return self.pre
题目：判断两颗多叉树关于叶子节点的前序遍历是否相等。
1 | 例子： 1 1 / / \ / \ 2 3 4 5 2 / \ / / \ 5 6 6 3 4 |
两棵树的前序遍历都是5->6->3->4
解法：实现后续迭代器
执行next函数，直到两者都为叶子结点，将叶子结点进行比较。
如果不等，则直接返回
如果相等，则继续执行2，直到迭代器都为空
代码地址：https://gist.github.com/senarukana/9d322716b2a86968deec