首页 > 试题广场 >

二叉树的后序遍历

[编程题]二叉树的后序遍历

热度指数：80895 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，返回他的后序遍历的序列。

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

数据范围：二叉树的节点数量满足 $1 \le n \le 100 \$ ，二叉树节点的值满足 $1 \le val \le 100 \$ ，树的各节点的值各不相同

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图

示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

pein531

迭代版后序遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        if(root == null) return new int[0];
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while(!stack1.isEmpty()){
            TreeNode node = stack1.pop();
            stack2.push(node);
            if(node.left != null) stack1.push(node.left);
            if(node.right != null) stack1.push(node.right);
        }
        int[] postOrderSeq = new int[stack2.size()];
        int idx = 0;
        while(!stack2.isEmpty()) postOrderSeq[idx ++] = stack2.pop().val;
        return postOrderSeq;
    }
}

发表于 2021-11-21 09:04:09 回复(2)

C++

远闻君

class Solution {
public:
    vector<int> ans;
public:
    void _showVal(TreeNode* root) {
        if (root) {
            _showVal(root->left);
            _showVal(root->right);
            ans.push_back(root->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        _showVal(root);
        return ans;
    }
};

发表于 2022-03-28 12:57:18 回复(0)

C++

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root ==nullptr)return res;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

发表于 2022-04-27 18:04:56 回复(0)

Python3

爱上咖啡

class Solution:

def postorderTraversal(self , root: TreeNode) -> List[int]:

# write code here

if root != None:

return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

return []

发表于 2025-07-11 17:36:37 回复(0)

求求来个offer可怜我吧

morris 后序时间O(n) 空间 O(1)

public int[] postorderTraversal(TreeNode root) {
         if (root == null) {
            return new int[0];
        }
        List<Integer> res = new ArrayList<>();
        TreeNode dummy = new TreeNode(0); // 虚拟根节点
        dummy.left = root;
        TreeNode curr = dummy;
        while (curr != null) {
            if (curr.left == null) {
                curr = curr.right;
            } else {
                TreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    // 逆序输出从 curr.left 到 pre 的路径
                    reverseAddNodes(curr.left, pre, res);
                    pre.right = null;
                    curr = curr.right;
                }
            }
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

// 辅助函数：逆序输出从 from 到 to 的路径节点
    private void reverseAddNodes(TreeNode from, TreeNode to, List<Integer> res) {
        reverse(from, to);
        TreeNode node = to;
        while (true) {
            res.add(node.val);
            if (node == from) break;
            node = node.right;
        }
        reverse(to, from);
    }

// 辅助函数：反转链表
    private void reverse(TreeNode from, TreeNode to) {
        TreeNode prev = null, curr = from;
        while (prev != to) {
            TreeNode next = curr.right;
            curr.right = prev;
            prev = curr;
            curr = next;
        }
    }

发表于 2025-07-09 22:12:48 回复(0)

StellarVibes

void fuc(struct TreeNode* root, int* arr,int * count)

{

if (root == NULL)

{

return;

}

fuc(root->left, arr,count);

fuc(root->right, arr,count);

arr[*count] = root->val;

//printf("%d ",arr[*count]);

//printf("%d\n",*count);

(*count)++;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize ) {

int* arr = (int*)malloc(sizeof(4)*1000);

int count = 0;

fuc(root, arr,&count);

//while(*arr)

//{

//printf("%d ",*arr);

//arr++;

//}

*returnSize=count;

return arr;

}

发表于 2024-12-14 18:30:27 回复(1)

Python3

Adam_Sun

非递归Python

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        cur = root
        res, stack = [], []
        while cur&nbs***bsp;stack:
            if cur:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.right
            else:
                cur = stack.pop()
                cur = cur.left
        return res[::-1]

发表于 2024-11-18 19:41:21 回复(0)

C++

岂能哭死董卓

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> result;
    //非递归算法
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* N=st.top();
            st.pop();
            if(N)
            result.push_back(N->val);
            else
             continue;
            st.push(N->left);
            st.push(N->right);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

发表于 2023-04-05 17:14:11 回复(0)

zipman

morris 后序时间O(n) 空间 O(1)

func postorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	cur, mostRight := root, &TreeNode{}
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right != cur {
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
                mostRight.Right = nil
				rN := reverseRight(cur.Left)
				cpRn := rN
				for rN != nil {
					res = append(res, rN.Val)
					rN = rN.Right
				}
				reverseRight(cpRn)
			
			}
		}
		cur = cur.Right
	}
	rN := reverseRight(root)
	cpRn := rN
	for rN != nil {
		res = append(res, rN.Val)
		rN = rN.Right
	}
	reverseRight(cpRn)

	return res
}
func reverseRight(root *TreeNode) *TreeNode {
	var pre *TreeNode
	for root != nil {
		cur := root
		root = root.Right
		cur.Right = pre
		pre = cur
	}
	return pre
}

发表于 2023-01-12 19:10:48 回复(0)

Java

键盘都敲坏了.

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {

        // 后序遍历: left -> right -> this

        // 存储后序遍历的结果
        List<Integer> arrayList = new ArrayList();
        // 后序遍历
        postDFS(root, arrayList);
        // 转int数组
        return arrayList.stream().mapToInt(i->i).toArray();
    }
    public void postDFS (TreeNode root, List<Integer> arrayList) {
        // 节点空，返回
        if(root == null){
            return;
        }
        // 向左遍历
        postDFS (root.left, arrayList);
        // 向右遍历
        postDFS (root.right, arrayList);
        // 存储当前节点
        arrayList.add(root.val);
    }

}

发表于 2022-11-01 13:53:53 回复(0)

Python3

StevenWqq

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        res = []
        
        def postorder(root):
            if not root:
                return
            if root.left:
                postorder(root.left)
            if root.right:
                postorder(root.right)
            res.append(root.val) 
            return
            
        postorder(root)
        return res

发表于 2022-06-01 11:28:18 回复(0)

快乐每一天2020

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

void postorderTraversalHelper(struct TreeNode* root, int* result, int* index) {
    if (root == NULL) {
        return;
    }
    
    // 后序遍历：左->右->根
    postorderTraversalHelper(root->left, result, index);
    postorderTraversalHelper(root->right, result, index);
    result[(*index)++] = root->val;
}

/**
 * 计算二叉树节点个数
 * @param root 根节点
 * @return 节点总数
 */
int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // 计算节点总数
    *returnSize = countNodes(root);
    
    // 分配结果数组
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    if (result == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    // 执行后序遍历
    int index = 0;
    postorderTraversalHelper(root, result, &index);
    
    return result;
}

发表于 2025-11-11 16:39:20 回复(0)

牛客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)

Daniel_shark

void traverse(int *res, struct TreeNode* root, int* returnSize)

{

if (root == NULL) {

return;

}

traverse(res, root->left, returnSize);

traverse(res, root->right, returnSize);

res[(*returnSize)++] = root->val;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize ) {

int *res = (int *)calloc(101, sizeof(int));

traverse(res, root, returnSize);

return res;

}

发表于 2025-05-27 16:08:39 回复(0)

咸鱼余号

public int[] postorderTraversal (TreeNode root) {
        // write code here
        if (root == null)
        {
            return new int[]{};
        }
        ArrayList<Integer> list = new ArrayList<>();
        end(root, list);
        return list.stream().filter(integer -> integer != null).mapToInt(i->i).toArray();
        
    }
    public void end (TreeNode root, ArrayList arr)
    {
        if (root.left != null)
        {
            end(root.left, arr);
        }
        if (root.right != null)
        {
            end(root.right, arr);
        }
        arr.add(root.val);
    }

发表于 2025-04-11 10:38:58 回复(0)

江南wl

public int[] postorderTraversal (TreeNode root) {

// write code here

if(root == null){

return new int[0];

}

List<Integer> a = new ArrayList();

solve(root, a);

int[] b = new int[a.size()];

for(int i = 0; i < b.length; i++){

b[i] = a.get(i);

}

return b;

}

private void solve(TreeNode node, List<Integer> a){

if(node.left != null){

solve(node.left, a);

}

if(node.right != null){

solve(node.right, a);

}

a.add(node.val);

}

发表于 2025-04-01 23:32:02 回复(0)

求求给个offer我什么都会做的

害面试时要是都出这种题就好了，直接默写

发表于 2025-03-11 21:19:29 回复(0)

MeetYiFan

function postorderTraversal( root ) {
    if(!root) return []
    return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
}

发表于 2025-02-16 00:12:59 回复(0)

在努力存钱的外卷侠很胆小

class Solution:

def postorderTraversal(self , root: TreeNode) -> List[int]:

# write code here

# if root.left==None and root.right==None and root!=None:

# print(root)

l=[]

def hou(root):

if root:

hou(root.left)

hou(root.right)

l.append(root.val)

hou(root)

return l

发表于 2024-12-27 15:53:26 回复(0)

Rust

老刘001

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @return int整型一维数组
    */
    pub fn postorderTraversal(&self, root: Option<Box<TreeNode>>) -> Vec<i32> {
        // write code here
        
        fn f(node: & Option<Box<TreeNode>>, v: &mut Vec<i32>) {
            if node.is_none() {return}
            f(&node.as_ref().unwrap().left, v);
            f(&node.as_ref().unwrap().right, v);
            v.push(node.as_ref().unwrap().val);
        }

        let mut v = Vec::new();
        f(&root,&mut v);
        v
    }

}

发表于 2024-08-15 23:11:00 回复(0)