leetcode做题记录 —— binary-tree-preorder-traversal

binary-tree-preorder-traversal 
Given a binary tree, return the preorder traversal of its nodes’ values’

For example: 
Given binary tree [1,null,2,3],

1.   1
2.    \
3.     2
4.    /
5.   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

binary-tree-preorder-traversal

给定一个二叉树，对其进行先序遍历，返回一个遍历结果的数组。

解法一，递归

1.//Javascript
2./**
3. * Definition for a binary tree node.
4. * function TreeNode(val) {
5. *     this.val = val;
6. *     this.left = this.right = null;
7. * }
8. */
9./**
10. * @param {TreeNode} root
11. * @return {number[]}
12. */
13.var preorderTraversal = function(root) {
14.    if(root === null)
15.    {
16.        return [];
17.    }
18.    return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)];
19.};

解法二，迭代

1.//Javascript
2./**
3. * Definition for a binary tree node.
4. * function TreeNode(val) {
5. *     this.val = val;
6. *     this.left = this.right = null;
7. * }
8. */
9./**
10. * @param {TreeNode} root
11. * @return {number[]}
12. */
13.var preorderTraversal = function(root) {
14.    let stack = [];
15.    let result = [];
16.    while( root !== null || stack.length > 0 )
17.    {
18.        if( root !== null )
19.        {
20.            stack.push(root);
21.            result.push(root.val);
22.            root = root.left;
23.        }
24.        else
25.        {
26.            root = stack.pop();
27.            root = root.right;
28.        }
29.    }
30.    return result;
31.};

解法三，Morris Traversal

来源 
也是使用循环，但是只用到了常量的空间

1.//Javascript
2./**
3. * Definition for a binary tree node.
4. * function TreeNode(val) {
5. *     this.val = val;
6. *     this.left = this.right = null;
7. * }
8. */
9./**
10. * @param {TreeNode} root
11. * @return {number[]}
12. */
13.var preorderTraversal  = function(root) {
14.    let result = [];
15.    let cur = root;
16.    let prev = null;
17.    while( cur !== null)
18.    {
19.        //当前遍历到的节点的左节点为空，
20.        //输出结果，并设置下一个遍历的节点为当前节点的右节点
21.        //因为预先把当前节点的索引赋值到了当前节点前驱的右节点上，所以直到遍历完整颗二叉树，右节点总不为空
22.        if( cur.left === null )
23.        {
24.            result.push(cur.val);
25.            cur = cur.right;
26.        }
27.        else
28.        {
29.            //找到当前节点的前驱结点
30.            //在中序遍历下，即为当前节点左节点的子节点中最右的节点
31.            //prev.right !== cur 非常重要，如果prev.right就是当前节点的话，说明在之前的过程中，已经把prev设置为前驱结点的前驱结点了
32.            prev = cur.left;
33.            while( prev.right !== null && prev.right !== cur )
34.            {
35.                prev = prev.right;
36.            }
37.            //如果前驱结点的右节点为空，说明是第一次遍历到，设置右节点为当前节点的索引
38.            //按照先序遍历的规则，输出当前的结果
39.            if( prev.right === null )
40.            {
41.                result.push(cur.val);
42.                prev.right = cur;
43.                cur = cur.left;
44.            }
45.            else
46.            {
47.                //前驱结点的右节点不为空，说明当前节点的左子树已经遍历完毕，并继续遍历右子树
48.                //并把前驱结点的右节点还原为原来的空值
49.                prev.right = null;
50.                cur = cur.right;
51.            }
52.        }
53.    }
54.    return result;
55.};

End