144. 二叉树的前序遍历（94 & 145） #33
Description
此题与94. 二叉树的中序遍历和145. 二叉树的后序遍历类似，解题思路基本一致，只是访问节点的先后顺序不同，因此放一起说明。
方法一：递归
解题思想：
前序遍历指的是依次访问根节点、左节点、右节点。因此按照顺序访问，并在左右节点递归调用就可以了。
递归终止的条件为碰到空节点。
代码：
前序遍历
var preorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问根节点
res.push(root.val);
// 再访问左节点
if (root.left) {
const leftRes = preorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 最后访问右节点
if (root.right) {
const rightRes = preorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
return res;
};中序遍历
var inorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问左节点
if (root.left) {
const leftRes = inorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 再访问根节点
res.push(root.val);
// 最后访问右节点
if (root.right) {
const rightRes = inorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
return res;
};后序遍历
var postorderTraversal = function(root) {
// 递归终止条件
if (root === null) {
return [];
}
const res = [];
// 先访问左节点
if (root.left) {
const leftRes = postorderTraversal(root.left);
leftRes.forEach(val => res.push(val));
}
// 再访问右节点
if (root.right) {
const rightRes = postorderTraversal(root.right);
rightRes.forEach(val => res.push(val));
}
// 最后访问根节点
res.push(root.val);
return res;
};复杂度分析：
- 时间复杂度：O(n)：其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度：O(n)：为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
方法二：迭代（栈）
解题思想：
完全可以利用栈的特性来模拟访问，先入栈根节点，出栈访问，再入栈右节点与左节点，按照顺序，出栈左节点和右节点即可。
代码：
前序遍历
var preorderTraversal = function (root) {
const res = [];
const stack = [];
if (root) stack.push(root);
while (stack.length > 0) {
const node = stack.pop();
res.push(node.val);
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return res;
};中序遍历
借助一个指针来指向当前节点，先一直遍历到左子节点，进行入栈
var inorderTraversal = function(root) {
if (!root) return [];
const res = [];
const stack = [];
let curr = root;
while (stack.length || curr) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
const node = stack.pop();
res.push(node.val)
if (node.right) {
curr = node.right
}
}
return res;
};后序遍历
后序遍历我们通过前序遍历来转换一下：前序遍历是根左右，把它变成根右左，然后反过来就是左右根，也就是后序遍历的遍历顺序。
var postorderTraversal = function(root) {
if (!root) return [];
const res = [];
const stack = [root];
while (stack.length) {
const node = stack.pop();
// 虽然我们要先遍历的是右子节点，但是因为栈的特性，所以要先入栈左子节点
if (node.left) {
stack.push(node.left);
}
res.push(node.val);
if (node.right) {
stack.push(node.right);
}
}
// 把结果反过来就是后序遍历的输出了
return res.reverse();
};复杂度分析：
其实和递归都是一样的。两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同。
方法三：Morris
解题思想：
Morris的通用解法过程：
Morris 的整体思路就是将 以某个根结点开始，找到它左子树的最右侧节点之后与这个根结点进行连接
我们可以从 图2 看到，如果这么连接之后，cur 这个指针是可以完整的从一个节点顺着下一个节点遍历，将整棵树遍历完毕，直到 7 这个节点右侧没有指向。
var preorderTraversal = function(root) {
if (root == null) {
return;
}
let cur1 = root;//当前开始遍历的节点
let cur2 = null;//记录当前结点的左子树
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {//找到当前左子树的最右侧节点，且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
cur2 = cur2.right;
}
if (cur2.right == null) {//这个时候如果最右侧这个节点的右指针没有指向根结点，创建连接然后往下一个左子树的根结点进行连接操作。
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {//当左子树的最右侧节点有指向根结点，此时说明我们已经回到了根结点并重复了之前的操作，同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点 了，把路断开。
cur2.right = null;
}
}
cur1 = cur1.right;//一直往右边走，参考图
}
}代码：
前序遍历
- 在某个根结点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。
- 打印某些自身无法创建连线的节点，也就是叶子节点。
var preorderTraversal = function(root) {
if (!root) return;
const res = [];
let cur1 = root; // 当前开始遍历的节点
let cur2; // 记录当前结点的左子树
while(cur1) {
cur2 = cur1.left;
if(cur2) {
// 找到当前左子树的最右侧节点，
// 且这个节点应该在指向根结点之前，否则整个节点又回到了根结点。
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
// 这个时候如果最右侧这个节点的右指针没有指向根结点，
// 创建连接然后往下一个左子树的根结点进行连接操作。
if (!cur2.right) {
cur2.right = cur1;
res.push(cur1.val);
cur1 = cur1.left;
continue;
} else { // 当左子树的最右侧节点有指向根结点，
// 此时说明我们已经回到了根结点并重复了之前的操作，
// 同时在回到根结点的时候我们应该已经处理完 左子树的最右侧节点了，把路断开。
cur2.right = null;
}
} else {
res.push(cur1.val);
}
// 一直往右边走
cur1 = cur1.right;
}
};中序遍历
从最左侧开始顺着右节点打印。也就是在将cu1切换到上层节点的时候。
var inorderTraversal = function(root) {
if (!root) return [];
const res = [];
let cur1 = root;
let cur2;
while(cur1) {
cur2 = cur1.left;
//构建连接线
if(cur2) {
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if (!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
}
res.push(cur1.val);
cur1 = cur1.right;
}
return res;
};后序遍历
当我们到达最左侧，也就是左边连线已经创建完毕了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我们将一个节点的连续右节点当成一个单链表来看待。
当我们返回上层之后，也就是将连线断开的时候，打印下层的单链表。
比如返回到 ２，此时打印 ４
比如返回到 １，此时打印 ５ ２
比如返回到 ３，此时打印 ６
那么我们只需要将这个单链表逆序打印就行了
这里不应该打印当前层，而是下一层，否则根结点会先与右边打印。
var postorderTraversal = function(root) {
if (!root) return [];
const res = [];
// 翻转单链表
const postMorrisReverseList = (root) => {
let cur = root;
let pre;
while (cur) {
let next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
};
// 打印函数
const postMorrisPrint = (root) => {
const reverseList = postMorrisReverseList(root);
let cur = reverseList;
while (cur) {
res.push(cur.val);
cur = cur.right;
}
postMorrisReverseList(reverseList);
};
let cur1 = root; // 遍历树的指针变量
let cur2; // 当前子树的最右节点
while(cur1) {
cur2 = cur1.left;
if(cur2) {
while (cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if (!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
postMorrisPrint(cur1.left);
}
}
cur1 = cur1.right;
}
postMorrisPrint(root);
return res;
};复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)