undefined

递归序：二叉树上的每个节点都会被遍历三次。

void f(TreeNode* root) {
	// 1
	if (root == nullptr) {
		return;
	}
	// 1 这里打印就是先序
	f(root->left);
	// 2
	// 2 这里打印就是中序
	f(root->right);
	// 3
	// 3 这里打印就是后序
}

如上注释，

• 先序：只在第一次来到当前节点时打印
• 中序：只在第二次来到当前节点时打印
• 后序：只在第三次来到当前节点时打印

任何递归函数都可以改成非递归。

先序非递归：（头左右）

1. 先将 root 节点压入栈中
2. 从栈中弹出一个节点 cur
3. 打印（处理）cur 节点
4. 先后再左（如果有）

后序遍历（非递归）：头左右是先序，我们可以实现 头右左。这时我们弹出时不打印，而是放在一个辅助栈中，那么最终辅助栈中的打印顺序就是 左右头。就是后序遍历

中序遍历：

• 整棵树左边界进栈
• 然后依次弹出节点的过程中，打印，然后对弹出节点的右树重复流程（这个右树的左边界进栈）

二叉树的宽度优先遍历（求一棵二叉树的宽度）也就是层序遍历。使用队列即可。先插入头节点，然后循环：从队列中取出来一个节点，打印，然后先放左节点，再放右节点。

判断二叉树是否平衡二叉树：1. 左子树是平衡二叉树 2. 右子树是平衡二叉树 3. 左右子树之间的高度差不超过 1

二叉树的递归套路：需要向子树要什么信息？树形DP：就是从左子树要信息，从右子树要信息。