LeetCode 94. 二叉树的中序遍历

题目链接：LeetCode 94. 二叉树的中序遍历

题意：

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

解题思路：

对于二叉树的遍历，有递归和非递归两种遍历方式，
1. 递归遍历
** 根据“左->根->右”的顺序，直接模拟即可。注意按照递归三部曲（递归的参数和返回值、递归的终止条件、单层递归的逻辑）**

递归代码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 var res []int
func inorderTraversal(root *TreeNode) []int {
res = []int{}
    pt(root)
    return res
}

func pt(root *TreeNode){
    if root == nil{
        return
    } 
    pt(root.Left)
    
    res = append(res,root.Val)
    pt(root.Right)
   
}

2. 迭代遍历

迭代代码如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
func inorderTraversal(root *TreeNode) []int {
    var res []int //结果数组
    var stk []*TreeNode  //栈
    for root != nil || len(stk)!= 0{ //当节点不空或者栈不空时
        for root != nil { //如果当前节点不空，入栈
            stk = append(stk,root) 
            root = root.Left  //当前节点移动到他的左子树上（遍历左子树）
        }
        // 循环结束后，root 指向的是最左最下节点的左孩子，即 nil节点
        root = stk[len(stk)-1]  //取出栈顶元素
        stk = stk[:len(stk)-1]  //出栈
        res = append(res,root.Val) //当前节点加入结果集 （遍历当前节点）
        root = root.Right  //遍历右子树
    }
    return res
}