144. 二叉树的前序遍历（94 & 145）

[swiftwind0405]

此题与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;//一直往右边走，参考图
	}
}

代码：

前序遍历

1. 在某个根结点创建连线的时候打印。因为我们是顺着左边的根节点来创建连线，且创建的过程只有一次。
2. 打印某些自身无法创建连线的节点，也就是叶子节点。

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)