144. 二叉树的前序遍历

题意：

解题思路：

思路：
1.从根节点出发，先将根节点存入栈中；
2.每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中；
3.先压入右孩子，再压入左孩子，为的是先弹出左孩子的值[左孩子在栈顶端]；

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 preorderTraversal($root) {
        return $this->stackPreorderTraversal($root);
        if ($root) {
            $this->res[] = $root->val;
            $this->preorderTraversal($root->left);
            $this->preorderTraversal($root->right);
        }
        return $this->res;
    }
    function stackPreorderTraversal($root) {
        if ($root == null) return [];
        $list = [];
        $stack = new SplStack();
        $stack->push($root);
        while (!$stack->isEmpty()) {
            $root = $stack->pop();
            $list[] = $root->val;
            if ($root->right != null) $stack->push($root->right);
            if ($root->left != null) $stack->push($root->left);
        }
        return $list;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
func preorderTraversal(root *TreeNode) []int {
    return stackPreOrderTraversal(root)
    res = []int{}
    dfs(root)
    return res
}
func dfs(root *TreeNode) {
    if root != nil {
        res = append(res, root.Val)
        dfs(root.Left)
        dfs(root.Right)
    }
}
func stackPreOrderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    var stack []*TreeNode
    stack = append(stack, root)
    var res []int
    for len(stack) > 0 {
        p := stack[len(stack) - 1]
        stack = stack[0 : len(stack) - 1]
        res = append(res, p.Val)
        if p.Right != nil {
            stack = append(stack, p.Right)
        }
        if p.Left != nil {
            stack = append(stack, p.Left)
        }
    }
    return res
}