94. 二叉树的中序遍历

leecode原题

题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例

示例 1:

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2:

输入：root = []
输出：[]

示例 3:

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶

递归算法很简单，你可以通过迭代算法完成吗？

解题思路

思路

递归实现

递归实现是比较简单的，记住左子树->根节点->右子树的遍历顺序即可，另外要当心golang里面切片传递的坑！

迭代实现

借用栈搞定，其实也简单，详见代码，有详细步骤。

实现

源码

递归实现

func inorderTraversal(root *TreeNode) []int {
    nodeArr := make([]int, 0)
    traversal(root, &nodeArr)
    return nodeArr
}

func traversal(cur_node *TreeNode, arr *[]int) {
    if cur_node == nil {
        return
    }
    traversal(cur_node.Left, arr)
    *arr = append(*arr, cur_node.Val)
    traversal(cur_node.Right, arr)
}

迭代实现

type Stack struct {
    elements []*TreeNode
}

func NewStack() *Stack {
    return &Stack{elements: make([]*TreeNode, 0)}
}

func (s *Stack) IsEmpty() bool {
    if len(s.elements) == 0 {
        return true
    }
    return false
}

func (s *Stack) Push(element *TreeNode) {
    s.elements = append(s.elements, element)
}

func (s *Stack) Pop() *TreeNode {
    if !s.IsEmpty() {
        res := s.elements[len(s.elements)-1]
        s.elements = s.elements[:len(s.elements)-1]
        return res
    }
    return nil
}

// 迭代遍历
func inorderTraversal(root *TreeNode) []int {
    nodeArr := make([]int, 0)
    if root == nil {
        return nodeArr
    }
    s := NewStack()
    // 步骤1: 直到当前结点为空 & 栈空时，循环结束
    for root != nil || !s.IsEmpty() {
        // 步骤2: 判断当前结点是否为空
        if root != nil {
            // 步骤3: 将该节点入栈
            s.Push(root)
            // 步骤4: 置当前结点的左孩子为当前节点
            root = root.Left
            // 返回步骤1
        } else {
            // 步骤5：出栈栈顶结点
            root = s.Pop()
            // 步骤6：保存节点
            nodeArr = append(nodeArr, root.Val)
            // 步骤7：置当前结点的右孩子为当前节点
            root = root.Right
            // 返回步骤1
        }
    }
    return nodeArr
}