[代码随想录]Day12-二叉树part01

WtcSky / 2023-08-08 / 原文

今天的题目就是二叉树的前中后序遍历，目前只写了递归方法，之后再补迭代方法。

题目：144. 二叉树的前序遍历

思路：

前序遍历：根-左-右

代码1：

递归，递归情况下只需要改变递归的顺序即可实现前中后序遍历。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
func preorderTraversal(root *TreeNode) []int {
    res = []int{}
    preorder(root)
    return res
}
func preorder(t *TreeNode) {
    if t == nil { // 空就返回
        return
    }
    res = append(res, t.Val) // 先遍历根节点
    preorder(t.Left) // 左节点
    preorder(t.Right) // 右节点
}

参考

代码随想录

题目：145. 二叉树的后序遍历

思路：

后序遍历：左-右-根

代码1：

递归，递归情况下只需要改变递归的顺序即可实现前中后序遍历。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 var res []int
func postorderTraversal(root *TreeNode) []int {
    res = []int{}
    postorder(root)
    return res
}
func postorder(t *TreeNode) {
    if t == nil { // 空就返回
        return
    }
    postorder(t.Left) // 左节点
    postorder(t.Right) // 右节点
    res = append(res, t.Val) // 最后遍历根节点
}

参考：

代码随想录

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

思路：

中序遍历：左-根-右

代码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{}
    inorder(root)
    return res
}
func inorder(t *TreeNode) {
    if t == nil {
        return
    }
    inorder(t.Left)
    res = append(res, t.Val)
    inorder(t.Right)
}