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

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

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

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

return [3,2,1].

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

binary-tree-postorder-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 postorderTraversal = function(root) {
14.    if(root === null)
15.    {
16.        return [];
17.    }
18.    return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val];
19.};
20.};

解法二，迭代

相比前序和中序遍历，后续遍历需要判断栈顶元素的右孩子是否已经访问过 
如果已经访问过，说明左右子树已经遍历完毕，按照后续遍历的规则，就可以输出结果。 
如果右孩子不为空并且没有访问过，就继续遍历右子树。

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 postorderTraversal = function(root) {
14.    let stack = [];
15.    let result = [];
16.    let prev = null;
17.    while( root !== null || stack.length > 0 )
18.    {
19.        if( root !== null )
20.        {
21.            stack.push(root);
22.            root = root.left;
23.        }
24.        else
25.        {
26.            //查看栈顶，
27.            //如果栈顶节点的右孩子不为空，并且右孩子不是上一次访问的节点，遍历右子树
28.            let stackTop = stack[stack.length - 1];
29.            if( stackTop.right !== prev && stackTop.right !== null )
30.            {
31.                root = stackTop.right;
32.            }
33.            else
34.            {
35.                //如果栈顶的右孩子为空，或者上一次访问的节点为右孩子
36.                //说明左右子树已经遍历完毕，按照后序遍历的规则，出栈，输出当前的值
37.                stack.pop();
38.                result.push(stackTop.val);
39.                prev = stackTop;
40.            }
41.        }
42.    }
43.    return result;
44.};

解法三，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} start
11. * @param {TreeNode} end
12. */
13.var reverse = function reverse(start, end) {
14.    if( start === end )
15.    {
16.        return;
17.    }
18.    let pre = start;
19.    let cur = start.right;
20.    let temp = null;
21.    while( pre !== end )
22.    {
23.        temp = cur.right;
24.        cur.right = pre;
25.        pre = cur;
26.        cur = temp;
27.    }
28.}
29./**
30. * @param {TreeNode} root
31. * @return {number[]}
32. */
33.var postorderTraversal  = function(root) {
34.    let result = [];
35.    let handle = new TreeNode("indifferent");
36.    handle.left = root;
37.    let cur = handle;
38.    let prev = null;
39.    while( cur !== null)
40.    {
41.        //当前遍历到的节点的左节点为空，
42.        //设置下一个遍历的节点为当前节点的右节点
43.        //因为预先把当前节点的索引赋值到了当前节点前驱的右节点上，所以直到遍历完整颗二叉树，右节点总不为空
44.        if( cur.left === null )
45.        {
46.            cur = cur.right;
47.        }
48.        else
49.        {
50.            //找到当前节点的前驱结点
51.            //为当前节点左节点的子节点中最右的节点
52.            //prev.right !== cur 非常重要，如果prev.right就是当前节点的话，说明在之前的过程中，已经把prev设置为前驱结点的前驱结点了
53.            prev = cur.left;
54.            while( prev.right !== null && prev.right !== cur )
55.            {
56.                prev = prev.right;
57.            }
58.            //如果前驱结点的右节点为空，说明是第一次遍历到，设置右节点为当前节点的索引
59.            if( prev.right === null )
60.            {
61.                prev.right = cur;
62.                cur = cur.left;
63.            }
64.            else
65.            {
66.                //前驱结点的右节点不为空，说明当前节点的左子树已经遍历完毕，并继续遍历右子树
67.                //并把前驱结点的右节点还原为原来的空值
68.                // 倒序输出当前节点左孩子到当前节点前驱结点之间的值
69.                reverse(cur.left, prev);
70.                let temp = prev;
71.                while( cur.left !== temp )
72.                {
73.                    result.push(temp.val);
74.                    temp = temp.right;
75.                }
76.                result.push(temp.val);
77.                reverse(prev, cur.left);
78.                prev.right = null;
79.                cur = cur.right;
80.            }
81.        }
82.    }
83.    return result;
84.};

End