二叉树的中序遍历

1. 题目描述

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

2. 思路

1. 思路一
   • 递归
2. 思路二
   • 颜色标记法

3. 实现

3.1. 递归

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

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

func inordered(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	inordered(root.Left, res)
	*res = append(*res, root.Val)
	inordered(root.Right, res)
}

3.2. 颜色标记法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

const (
    ColorWhite = 0
    ColorGray = 1
)

type Node struct {
    node *TreeNode
    color int
}

func inorderTraversal(root *TreeNode) []int {
    stack := make([]*Node, 0)
    stack = append(stack, &Node{node:root, color: ColorWhite})
    res := make([]int, 0)
    for len(stack) > 0 {
        pop := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if pop.node == nil {
            continue
        } 
        if pop.color == ColorWhite {
            stack = append(stack, &Node{node:pop.node.Right, color:ColorWhite})
            stack = append(stack, &Node{node:pop.node, color:ColorGray})
            stack = append(stack, &Node{node:pop.node.Left, color:ColorWhite})
        }else {
            res = append(res, pop.node.Val)
        }
    }
    return res
}

4. 参考

• 颜色标记法-一种通用且简明的树遍历方法 - 二叉树的中序遍历 - 力扣（LeetCode）