• 前序遍历、中序遍历、后序遍历它们的迭代、递归操作。
• 在树的遍历中存在回溯
• 二叉树的回溯是自底向上，因为先处理两个叶子节点，再处理根节点。

如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？
搜索一条边的写法：

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

搜索整个树写法：

left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;

看出区别了没？
「在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）」。

关于使用 ArrayDeque 和 LinkedList

各类操作的时间复杂度如下：

操作	ArrayDeque	LinkedList
头尾新增元素
修改元素
删除元素
查找元素

• LinkedList 会消耗更多内存，因为每个节点需要持有前向节点 prev 和后向节点的引用。
• LinkedList 的唯一优势是删除操作。时间复杂度为 。
• LinkedList 支持 null 元素，而 ArrayDeque 不支持。
• ArrayDeque 扩容时是旧数组长度的两倍，可能需要更多的内存。