94. 二叉树的中序遍历

题意：

解题思路：

思路：
1. 递归算法：中序遍历过程的顺序是 左 -> 根 -> 右;
2. 迭代算法：维护一个栈，把左边的元素全部放入栈中，然后再从栈中弹出元素，再压入右边元素;

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

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
func inorderTraversal(root *TreeNode) []int {
    res = make([]int, 0)
    dfs(root)
    return res
}
func dfs(root *TreeNode) {
    if root != nil {
        dfs(root.Left)
        res = append(res, root.Val)
        dfs(root.Right)
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    for 0 < len(stack) || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        n := stack[len(stack)-1] // pop
        stack = stack[:len(stack)-1]
        res = append(res, n.Val)
        root = n.Right
    }
    return res
}