144.二叉树的前序遍历——medium - 《leetcode》

给定一个二叉树，返回它的前序遍历。

示例:
**
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal

思路:

递归

前序遍历顺序：根节点——左子树————右子树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质。
时间复杂度O(n)
空间复杂度O(n)

迭代

使用栈模拟递归过程，对于栈顶元素，先压入右儿子，再压入左儿子，保证前序遍历顺序。
时间复杂度O(n)
空间复杂度O(n)

Mirrors遍历
Mirrors遍历原理 cur：当前遍历的指针
rightMost：cur节点的左子树的最右节点
1. 如果cur左子树为空：cur=cur.right;
2. 如果cur左子树不为空：找到rightMost
  ——1）如果rightMost.right=null，那么令rightMost=cur, cur=cur.left;
  ——2）否则，不为空则说明rightMost.right曾经被修改过，我们这是第二次来到这个点，修改rightMost.right=null,cur=cur.right;
解释一下上面的步骤：
1. 首先整体向左走，如果没有左子树向右走。
2. 如果左子树不为空，那么就找到左子树上最右的节点。这个节点的右子树一定是空的。把这个空指针指向当前节点，即保存了一个指向父节点的指针。此时，左子树还有值没有访问，cur向左走。
3. 3 中的结果是rightMost遍历到这个节点的，cur指针也会遍历到这个节点，这就是第二次访问到了，那么此时该节点作为rightMost时，是被修改过的，所以我们要重新修改其为null。
4. 当出现3的情况时，说明该节点的左子树全部访问完毕，所以此时cur向右走。
5. cur是真正有效的移动指针，它会走过所有的节点，rightMost是为了修改指针而存在的。

假设当前遍历到的节点为 x

如果 x 无左孩子，先将 x 的值加入答案数组，再访问 x 的右孩子，即 x=x.right。
如果 x 有左孩子，则找到 x 左子树上最右的节点（即左子树中序遍历的最后一个节点，x 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。
如果 predecessor 的右孩子为空，说明还未遍历过x的左子树，将x的值加入答案。然后将其右孩子指向x，然后访问 x 的左孩子，即 x=x.left。
如果 predecessor 的右孩子不为空，说明我们已经遍历完 x 的左子树，我们将 predecessor 的右孩子置空，然后访问 x 的右孩子，即x=x.right。
重复上述操作，直至访问完整棵树。

如果 predecessor 的右孩子不为空， ```javascript //递归版 var preorderTraversal = function (root) { let ans = []; const dfs = (root) => {
```
 if (root === null) return;
 ans.push(root.val);
 dfs(root.left);
 dfs(root.right);
```
}; dfs(root); return ans;

}; //迭代版 var preorderTraversal = function (root) { if (root === null) return []; let ans = []; let stack = [root]; while (stack.length) { let root = stack.pop(); ans.push(root.val); if (root.right !== null) { stack.push(root.right); } if (root.left !== null) { stack.push(root.left); } } return ans; }; //mirror遍历 var preorderTraversal = function (root) { let ans = []; while (root) { if (root.left !== null) { let pre = root.left; while (pre.right !== null && pre.right !== root) { pre = pre.right; } if (pre.right !== null) { pre.right = null; root = root.right; } else { ans.push(root.val); pre.right = root; root = root.left; } } else { ans.push(root.val); root = root.right; } } return ans; }; ```