目录
前序遍历
递归版本
迭代版本
中序遍历
递归版本
迭代版本
后序遍历
递归版本
迭代版本
二叉树层序遍历
栈的定义 语法注意：
Deque
Deque
为什么不用stack 参考 liuyubobobo 老师编写的 Java 程序员，别用 Stack？！
前序遍历
根左右 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。
递归版本
class Solution {
List res = new ArrayList<>();
public List preorderTraversal(TreeNode root) {
preorder(root);
return res;
}
//递归版本前序遍历
void preorder(TreeNode root){
if(root==null) return;
res.add(root.val);
preorder(root.left);
preorder(root.right);
}
}
时间复杂度：O(n)，其中n是二叉树的结点数，每一个节点恰好被遍历了一遍。空间复杂度：O(n)，为递归过程中栈的开销，平均情况是O(logn)，最坏情况下树呈现链状，为O(n)。
迭代版本
可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同。
class Solution {
public List preorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Deque stack = new ArrayDeque<>();
TreeNode node = root;
while(!stack.isEmpty() || node!=null){
while(node!=null){
res.add(node.val); //访问左节点的时候加入结果list
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return res;
}
}
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
中序遍历
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
递归版本class Solution {
List res = new ArrayList<>();
public List inorderTraversal(TreeNode root) {
inorder(root);
return res;
}
void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);
res.add(root.val);
inorder(root.right);
}
}
时间复杂度：O(n)，其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。
迭代版本递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Deque stack = new ArrayDeque<>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val); //访问左节点之后加入结果列表
root = root.right;
}
return res;
}
}
时间复杂度：O(n)，其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。
后序遍历
二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
递归版本class Solution {
List res = new ArrayList<>();
public List postorderTraversal(TreeNode root) {
postorder(root);
return res;
}
void postorder(TreeNode root){
if(root==null) return;
postorder(root.left);
postorder(root.right);
res.add(root.val);
}
}
迭代版本
与中序的不同之处在于：
中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。
当访问完一棵子树的时候，我们用prev指向该节点。这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。
class Solution {
public List postorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Deque stack = new ArrayDeque<>();
TreeNode prev = null;
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
root = stack.pop();
//已经访问完左子树 引入prev判断右子树是否访问过
if(root.right==null || root.right == prev){
res.add(root.val);
prev = root;
root = null;
}else{
stack.push(root); //先不访问当前节点，先压栈
root = root.right;
}
}
return res;
}
}
时间复杂度：O(n)，其中 n是二叉搜索树的节点数。每一个节点恰好被遍历一次。空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为O(logn)，最坏情况下树呈现链状，为 O(n)。
二叉树层序遍历
使用【数据结构】队列 辅助
class Solution {
public List> levelOrder(TreeNode root) {
List> res = new ArrayList<>();
if(root==null) return res;
Queue q = new linkedList<>();
q.offer(root);
while(!q.isEmpty()){
int sz = q.size();
List level = new ArrayList<>();
for(int i=0;i
记树上所有节点的个数为 n。时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。空间复杂度：队列中元素的个数不超过 nn 个，故渐进空间复杂度为 O(n)。
