中序遍历为左根右的顺序

理解不了，画个简单的二叉树图，照代码看栈内数据变化就明白了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    // 中序遍历为左根右
    results := make([]int, 0)
    stack := make([]*TreeNode, 0)
    curr := root
    for len(stack) != 0 || curr != nil {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        preNode := stack[len(stack) - 1]
        results = append(results, preNode.Val)
        // 数组模拟出栈
        stack = stack[:len(stack) - 1]
        // 当为右子节点时，preNode.Right==nil，则for != nil循环跳过，直接继续出栈，出的就是根节点了
        // 而根节点时，preNode.Right不为空，则右子树又继续被for != nil 循环执行，节点被压入栈中
        curr = preNode.Right
    }
    return results
}