145. 二叉树的后序遍历

题意：

解题思路：

思路：[123] => [132] =>反转后[231]
1.从根节点出发，先将根节点存入列表中；
2.入栈左节点，再入栈右节点；
3.弹出右节点，再对左节点进行迭代，重复上述过程； 
4.对列表集进行反转；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    public $res = [];
    function postorderTraversal($root) {
        return $this->stackPostorderTraversal1($root);
        if ($root) {
            $this->postorderTraversal($root->left);
            $this->preorderTraversal($root->right);
            $this->res = $root->val;
        }
        return $this->res;
    }
    function stackPostorderTraversal($root) {
        if ($root == null) return [];
        $list = [];
        $stack = new SplStack;
        while (!$stack->isEmpty() || $root != null) {
            if ($root != null) {
                $list[] = $root->val;
                $stack->push($root);
                $root = $root->right;
            } else {
                $root = $stack->pop();
                $root = $root->left;
            }
        }
        $this->reverse($list);
        return $list;
    }
    function reverse(&$list) {
        $l = 0; $r = count($list) - 1;
        while ($l <= $r) {
            $t = $list[$l];
            $list[$l] = $list[$r];
            $list[$r] = $t;
            $l++;
            $r--;
        }
    }
    function stackPostorderTraversal1($root) {
        if ($root == null) return [];
        $list = [];
        $stack = new SplStack; 
        $stack->push($root);
        while (!$stack->isEmpty()) {
            $cur = $stack->pop();
            array_unshift($list, $cur->val);
            if ($cur->left != null) $stack->push($cur->left);
            if ($cur->right != null) $stack->push($cur->right);
        }
        return $list;
    } 
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
func postorderTraversal(root *TreeNode) []int {
    return stackPostorderTraversal(root)
    res = []int{}
    dfs(root)
    return res
}
func dfs(root *TreeNode) {
    if root != nil {
        dfs(root.Left)
        dfs(root.Right)
        res = append(res, root.Val)
    }
}
func stackPostorderTraversal(root *TreeNode) []int {
    var res []int
    var stack = []*TreeNode{root}
    for len(stack) > 0 {
        if root != nil {
            res = append(res, root.Val)
            //栈的原理是先进后出
            stack = append(stack, root.Left) //先入栈左节点，最先弹出的是右边节点
            stack = append(stack, root.Right) //再入栈右节点，优先弹出右节点
        }
        index := len(stack) - 1
        root = stack[index] //弹出栈顶元素
        stack = stack[:index]  //继续遍历栈顶下面的元素
    }
    //反转，对前序遍历进行反转，[123] => [132], 反转后得到=>[231]
    l, r := 0, len(res) - 1
    for l < r {
        res[l], res[r] = res[r], res[l]
        l++
        r--
    }
    return res
}