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

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

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

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

return [1,3,2].

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

binary-tree-inorder-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 inorderTraversal = function(root) {
14.    if(root === null)
15.    {
16.        return [];
17.    }
18.    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(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 inorderTraversal = 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.            root = root.left;
22.        }
23.        else
24.        {
25.            root = stack.pop();
26.            result.push(root.val);
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 inorderTraversal = 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.            if( prev.right === null )
39.            {
40.                prev.right = cur;
41.                cur = cur.left;
42.            }
43.            else
44.            {
45.                //前驱结点的右节点不为空，说明当前节点的左子树已经遍历完毕，按照中序遍历的规则，输出当前的结果，并继续遍历右子树
46.                //并把前驱结点的右节点还原为原来的空值
47.                prev.right = null;
48.                result.push(cur.val);
49.                cur = cur.right;
50.            }
51.        }
52.    }
53.    return result;
54.};

End