首页 > 试题广场 >

二叉树的后序遍历

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

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

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

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图
示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
pein531头像 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)
zipman头像 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)
在吃瓜的00后很想去夏威夷头像 在吃瓜的00后很想去夏威夷
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整型一维数组
     */
    List<Integer> list=new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list=postOrder(root);
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++)
        {
            res[i]=list.get(i);
        }
        return res;
    }
    List<Integer> postOrder(TreeNode node)
    {
        if(node==null)
        {
            return list;
        }
        postOrder(node.left);
        postOrder(node.right);
        list.add(node.val);
        return list;
    }
    }
发表于 2024-04-12 20:19:20 回复(0)
JavaScript Node
陈彬杰a头像 陈彬杰a 
function postorderTraversal( root ) {
    if (!root) return [];
    return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
}

编辑于 2024-04-08 15:22:51 回复(0)
老还好了头像 老还好了
后序是“左右根”，其实把前序换成“根右左”，然后反转就是后序了，具体代码如下 
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 {

    private List<Integer> list = new ArrayList();


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            if(cur!=null) {
                list.add(cur.val);
                stack.push(cur);
                cur = cur.right;
            } else{
                cur = stack.pop();
                cur = cur.left;
            }
        }
        int len = list.size();
        int[] result = new int[len];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(len -i-1);
        }
        return result;
    }
}


发表于 2024-04-02 12:08:33 回复(0)
Java
你好，侦探先生头像 你好，侦探先生 
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整型一维数组
     */
    ArrayList<Integer> integers = new ArrayList<Integer>();

    public int[] postorderTraversal (TreeNode root) {
        // write code here
        tran(root);
        int[] result = new int[integers.size()];
        for (int i = 0; i < integers.size(); i++) {
            result[i] = integers.get(i);
        }
        return result;
    }

    public void tran(TreeNode node) {

        if (node != null) {
            tran(node.left);
            tran(node.right);
            integers.add(node.val);
        }
    }
}

编辑于 2024-03-27 14:37:38 回复(0)
C++
无问西东gmy头像 无问西东gmy 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        if (root) {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            postorder.push_back(root->val);
        }
        return postorder;
    }
  private:
    vector<int>postorder;
};

编辑于 2024-03-16 19:34:51 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
void postorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) {
    if(root->left!=NULL) 
        postorderTraver(root->left, res, StaticReturnSize);
    if(root->right!=NULL) 
        postorderTraver(root->right, res, StaticReturnSize);
    res[(*StaticReturnSize)++] = root->val;
}    
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    static int res[1000]={0}, StaticReturnSize=0;
    if(root==NULL) 
        return NULL;
    postorderTraver(root, res, &StaticReturnSize);
    *returnSize = StaticReturnSize;
    return res;
}

编辑于 2024-03-16 16:01:01 回复(0)
C
就要上岸了的秋招人很用心头像 就要上岸了的秋招人很用心 
void postOrder(struct TreeNode* root, int** a, int* count) {
    if (root != NULL) {
        postOrder(root->left, a, count);
        postOrder(root->right, a, count);
        (*a)[(*count)++] = root->val;
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = malloc(sizeof(int) * 1001);
    int count = 0;
    postOrder(root, &a, &count);
    *returnSize = count;
    int* result = malloc(sizeof(int) * count);
    memcpy(result, a, sizeof(int) * count);
    free(a);
    return result;
}

编辑于 2024-03-11 18:46:09 回复(0)
Java
咖啡滑滑子头像 咖啡滑滑子
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
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pre = null;
        while(root!=null || !s.isEmpty()){
            while(root!=null){
                s.push(root);
                root = root.left;
            }
            TreeNode node = s.peek();
            if(node.right == null || node.right ==  pre ){
                list.add(node.val);
                pre = node;
                s.pop();
            }else{
                root = node.right;
            }
        }
        return  list.stream().mapToInt(i->i).toArray();            
    }
}
发表于 2023-12-26 17:13:31 回复(0)
Leeston520头像 Leeston520
 // 后续遍历时 Left --> Right --> Root
    public int[] postorderTraversal(TreeNode root) {
        // write code here
        if (root == null)
            return new int[0];

        int len = 1;
        int[] leftArr = new int[0];
        int[] rightArr = new int[0];
        // 左边不为空, 则记录左边数组
        if (null != root.left) {
            leftArr = postorderTraversal(root.left);
            len += leftArr.length;
        }
        // 右边不为空，则记录右边数组
        if (null != root.right) {
            rightArr = postorderTraversal(root.right);
            len += rightArr.length;
        }
        int[] resInt = new int[len];
        // 装填左边
        for (int i = 0; i < leftArr.length; i++)
            resInt[i] = leftArr[i];
        // 装填右边
        for (int i = 0; i < rightArr.length; i++)
            resInt[leftArr.length + i ] = rightArr[i];

        // 装填 root
        resInt[leftArr.length + rightArr.length] = root.val;
        // 返回数组
        return resInt;
    }
发表于 2023-11-30 10:03:46 回复(0)
余生还长着呢头像 余生还长着呢 
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
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list.stream().mapToInt(i->i).toArray();
    }

    private void preOrder(TreeNode node,List<Integer> list){
        if(node == null){
            return;
        }
       
        preOrder(node.left,list);
        preOrder(node.right,list);
        list.add(node.val);
    }
}

发表于 2023-11-21 17:30:08 回复(0)
Java
李克雷头像 李克雷 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        if (null == root) {
            return new int[] {};
        }
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> nums = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            nums.add(0, top.val);
            if (top.left != null) {
                stack.push(top.left);
            }
            if (top.right != null) {
                stack.push(top.right);
            }
        }
        return list2Array(nums);
    }

    /**
     *  List<Integer>转化为int[]
     *
     *
     * @param nums List<Integer>类
     * @return int整型一维数组
     */
    public int[] list2Array(List<Integer> nums) {
        int[] numArray = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            numArray[i] = nums.get(i);
        }
        return numArray;
    }

}

发表于 2023-10-12 12:35:32 回复(0)
C
陈让然头像 陈让然
方法一：递归 
 int count=0;
 int arr[101];

void postOrder(struct TreeNode*root,int*arr)
{
    if(root)
    {
        postOrder(root->left,arr);
        postOrder(root->right,arr);
        arr[count++]=root->val;
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    // write code here
    postOrder(root,arr);
    *returnSize=count;
    return arr;
}
方法二：栈 
struct TreeNode*stack[100];
int arr[101];
int count=0;
int top=-1;

//记录上一个访问的节点
struct TreeNode* prev = NULL;

//入栈
void push(struct TreeNode*node)
{
    stack[++top]=node;
}
//出栈
struct TreeNode* pop(void)
{
    return stack[top--];
}
//后序遍历  左->右->根
//用栈实现，先进后出
int* postorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    // write code here
    if(!root)
    {
        *returnSize=0;
        return NULL;
    }

    while(root||top!=-1)
    {
        while(root)
        {    
            push(root);
            root=root->left;
        }

        root=stack[top];

        //如果栈顶元素的右节点为空或者已经访问过，则可以访问根节点
        if (!root->right || root->right == prev) 
        {
            //根节点存在，保存val
            arr[count++] = root->val;
            //记录上一个访问的节点
            prev = root;
            //栈顶元素出栈
            root = pop();
            //将根节点置为NULL，避免再次访问
            root = NULL;
        } 
        else 
        {
            //开始遍历右节点
            root = root->right;
        }

    }
    *returnSize=count;
    return arr;  
}
发表于 2023-09-17 16:08:39 回复(0)
C++
牛客706368877号头像 牛客706368877号
递归效率太低。 
/**
 * 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> postorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode*> st;
        vector<int> vec;
        TreeNode *node = root, *stTop;
        if (root != nullptr) {
            st.push(root);
        }

        while (!st.empty()) {
            stTop = st.top();
            if (stTop->right == node 
                || (stTop->right == nullptr && stTop->left == node)
                || (stTop->left == nullptr && stTop->right == nullptr)) {
                st.pop();
                node = stTop;
                vec.push_back(node->val);
            } else {
                if (stTop->right != nullptr) {
                    st.push(stTop->right);
                }
                if (stTop->left != nullptr) {
                    st.push(stTop->left);
                }
            }
        }

        return vec;
    }
};


发表于 2023-09-16 15:53:59 回复(0)
C
A202302282044461头像 A202302282044461
 int count = 0;
 int arr[100];
 void post_order(struct TreeNode * root, int * arr)
 {
    if (root != NULL) {
        post_order(root->left, arr);
        post_order(root->right, arr);
        arr[count++] = root->val;
    }
 }
int* postorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    post_order(root, arr);
    *returnSize = count;
    return arr;
}
发表于 2023-09-13 13:05:46 回复(0)
JavaScript Node
达拉崩吧、头像 达拉崩吧、 
function postorderTraversal(root) {
    // write code here
    let result = [];
    function postorder(root){
        if(!root)
            return;
        postorder(root.left);
        postorder(root.right);
        result.push(root.val);
    }
    postorder(root);
    return result;
}

发表于 2023-08-29 21:49:45 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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