首页 > 试题广场 >

二叉树的后序遍历

[编程题]二叉树的后序遍历
  • 热度指数：80969 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 ，二叉树节点的值满足 ，树的各节点的值各不相同

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图
示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Go
牛客720720643号头像 牛客720720643号 
package main
import . "nc_tools"

func postorderTraversal(root *TreeNode) (ans []int) {
    traversal(root, &ans)
    return
}

func traversal(node *TreeNode, ans *[]int) {
    if node != nil {
        traversal(node.Left, ans)
        traversal(node.Right, ans)
        *ans = append(*ans, node.Val)
    }
}
发表于 2025-10-07 17:53:37 回复(0)
Go
PeterLee6688头像 PeterLee6688 
func postorderTraversal( root *TreeNode ) []int {
    // write code here
    var res []int
    postorder(&res, root)
    return res
}

func postorder(list *[]int, root *TreeNode){
    if root == nil{
        return
    }
    postorder(list, root.Left)
    postorder(list, root.Right)
    *list = append(*list, root.Val)

}

发表于 2024-05-19 13:17:34 回复(0)
Go
牛客45680046号头像 牛客45680046号
package main

import . "nc_tools"

import (
    "container/list"
)

/**
BM25 二叉树的后序遍历
*/

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)

    // return postorder1(root, res)
    // return postorder2(root, res)
    return postorder3(root, res)
}

func postorder1(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }
    nums = postorder1(root.Left, nums)
    nums = postorder1(root.Right, nums)
    nums = append(nums, root.Val)
    return nums
}

// postorder2 需要存储已经遍历过右子树的父节点
func postorder2(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    m := make(map[*TreeNode]struct{})
    stack := list.New()
    p := root
    for stack.Len() != 0 || p != nil {
        for p != nil {
            stack.PushBack(p)
            p = p.Left
        }
        top := stack.Back().Value.(*TreeNode)
        if _, ok := m[top]; ok {
            nums = append(nums, top.Val)
            stack.Remove(stack.Back())
            p = nil
        } else {
            p = top.Right
            m[top] = struct{}{}
        }
    }

    return nums
}

// postorder3 相比2，实际上只需要存储本次处理的子树的root节点就好
func postorder3(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    stack := list.New()
    last := root
    p := root
    for stack.Len() != 0 || p != nil {
        for p != nil {
            stack.PushBack(p)
            p = p.Left
        }
        top := stack.Back().Value.(*TreeNode)
        if top.Right == nil || top.Right == last {
            nums = append(nums, top.Val)
            stack.Remove(stack.Back())
            p = nil
        } else {
            p = top.Right
        }
        last = top
    }

    return nums
}


import . "nc_tools"

import (
    "container/list"
)

/**
BM25 二叉树的后序遍历
*/

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)

    // return postorder1(root, res)
    // return postorder2(root, res)
    return postorder3(root, res)
}

func postorder1(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }
    nums = postorder1(root.Left, nums)
    nums = postorder1(root.Right, nums)
    nums = append(nums, root.Val)
    return nums
}

// postorder2 需要存储已经遍历过右子树的父节点
func postorder2(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    m := make(map[*TreeNode]struct{})
    stack := list.New()
    p := root
    for stack.Len() != 0 || p != nil {
        for p != nil {
            stack.PushBack(p)
            p = p.Left
        }
        top := stack.Back().Value.(*TreeNode)
        if _, ok := m[top]; ok {
            nums = append(nums, top.Val)
            stack.Remove(stack.Back())
            p = nil
        } else {
            p = top.Right
            m[top] = struct{}{}
        }
    }

    return nums
}

// postorder3 相比2，实际上只需要存储本次处理的子树的root节点就好
func postorder3(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    stack := list.New()
    last := root
    p := root
    for stack.Len() != 0 || p != nil {
        for p != nil {
            stack.PushBack(p)
            p = p.Left
        }
        top := stack.Back().Value.(*TreeNode)
        if top.Right == nil || top.Right == last {
            nums = append(nums, top.Val)
            stack.Remove(stack.Back())
            p = nil
        } else {
            p = top.Right
        }
        last = top
    }

    return nums
}

发表于 2022-11-27 16:09:33 回复(0)
Go
hzmg头像 hzmg
和前序中序遍历相同，只需要更换插入切换的顺序即可 
func postorderTraversal( root *TreeNode ) []int {

	result := make([]int, 0)
	var def func(root *TreeNode)
	def = func(root *TreeNode) {
		if root == nil {
			return
		}
		def(root.Left)
		
		def(root.Right)
        result = append(result, root.Val)
	}
	def(root)
	return result

    // write code here
}

发表于 2022-11-08 14:47:41 回复(0)
Go
admxt头像 admxt
package main
// import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
*/
func postorderTraversal( root *TreeNode ) []int {
    // write code here
    ret:=[]int{}
    if root!=nil{
        ret=append(ret,postorderTraversal(root.Left)...)
        ret=append(ret,postorderTraversal(root.Right)...)
        ret=append(ret,root.Val)
    }
    return ret
}
发表于 2022-03-31 11:01:13 回复(0)
Go
codewind头像 codewind 
package main
// import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
*/
func postorderTraversal( root *TreeNode ) []int {
    // write code here
    dfs(root)
    return p[:cnt]
}
var p [100]int
var cnt int

func dfs(root *TreeNode) {
    if root == nil {
        return 
    }
    dfs(root.Left)
    dfs(root.Right)
    p[cnt] = root.Val
    cnt++
    
}

发表于 2022-01-15 00:22:16 回复(0)
提交观点

问题信息

树 dfs 递归 广度优先搜索(BFS)
难度：
6条回答 8413浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的后序遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号