https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

难度：中等

---

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

示例:

  输入: [1,null,2,3]

1
 \
  2
 /
3

  输出: [1,2,3]

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

解法1：迭代

  能使用递归完成的算法，一般也能使用迭代来完成，递归其实就是使用了栈来保存当前的上下文环境，因此可以自定义栈来保存所需的环境 + 迭代来完成。

  对于前序遍历来说，我们需要保存的上下文环境就是遍历路径上的父节点。

  因此，按照前序遍历，从根结点开始，一直往左走，并将路径上的节点保存在栈中，当左孩子节点为空时，从栈中弹出父节点，并开始往右边走。

JS 代码：

var preorderTraversal = function(root) {
    let res = [];
    let st = [];
    let node = root;
    if (!root) {
        return res;
    }

    while (node || st.length) {
        // 一直往左走，直到左孩子结点为空
        while (node) {
            st.push(node);
            res.push(node.val);
            node = node.left;
        }
        // 开始往右走
        node = st.pop();
        node = node.right;
    }

    return res;
};

C 代码：

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* res = malloc(sizeof(int) * 2001);
    struct TreeNode* st[2001];
    int top = 0;
    *returnSize = 0;
    if (!root) {
        return res;
    }
    struct TreeNode* node = root;

    while (top || node) {
        // 一直往左走，直到左孩子结点为空
        while (node) {
            res[(*returnSize)++] = node->val;
            st[top++] = node;
            node = node->left;
        }
        // 开始往右走
        node = st[--top];
        node = node->right;
    }

    return res;
}

解法2：Morris 算法

  Morris 算法是一种能在线性时间内且只使用常数空间来实现树的遍历。

  Morris 算法对于三种顺序（前、中、后）的遍历，主要区分点在于访问节点的时机 。

  了解了 Morris 算法的原理后，要进行前序遍历，节点访问的时机主要有两个：

• 时机1：在创建当前节点左子树最右下结点的右指针时，访问当前节点
• 时机2：在需要借助最右下结点的右指针返回时，访问这个最右下结点

访问时机可结合代码来理解，建议自己手动模拟一遍来帮助理解

JS 代码：

var preorderTraversal = function(root) {
    let res = [];
    let node = root;
    if (!root) {
        return res;
    }

    while (node) {
        let left = node.left;
        if (left) {
            while (left.right && left.right !== node) {
                left = left.right;
            }
            if (!left.right) {
                // 时机1
                res.push(node.val);
                left.right = node;
                node = node.left;
                continue;
            } else {
                left.right = null;
            }
        } else {
            // 时机2
            res.push(node.val);
        }
        node = node.right;
    }

    return res;
};