首页 > 试题广场 >

二叉树的后序遍历

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

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

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

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图
示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
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

        // 1.初始化一个ArrayList用于动态添加数据
        ArrayList<Integer> resultList = new ArrayList<>();

        // 2.调用后序遍历递归函数
        process(resultList, root);

        // 3.将ArrayList转换成int[]并返回
        return listToArray(resultList);
    }

    // 后序遍历递归函数
    public void process(ArrayList<Integer> resultList, TreeNode root) {
        if (root == null) {
            return;
        }
        process(resultList, root.left);
        process(resultList, root.right);
        resultList.add(root.val);
    }

    // ArrayList转int[]
    public int[] listToArray(ArrayList<Integer> resultList) {
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
}

发表于 2024-07-29 19:02:34 回复(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)
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)
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)
Java
DDwu头像 DDwu 
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
    //     if (root == null) return new int[0];
    //     postorder(root);
    //     int[] res = new int[list.size()];
    //     for(int i = 0; i<list.size(); i++){
    //         res[i]=list.get(i);
    //     }
    //     return res;
    // }
    // public void postorder (TreeNode root) {
    //     // write code here
    //     if (root != null) {
    //         postorderTraversal(root.left);
    //         postorderTraversal(root.right);
    //         list.add(root.val);
    //     }
    // }
      /**
        非递归
     */
     public int[] postorderTraversal (TreeNode root) {
        if (root==null) return new int[0];
        Stack<TreeNode> s1=new Stack<>();
        Stack<TreeNode> s2=new Stack<>();
        TreeNode cur=root;
        s1.push(cur);
        while(!s1.empty()){
            cur=s1.pop();
            s2.push(cur);
            if(cur.left!=null) s1.push(cur.left);
            if(cur.right!=null) s1.push(cur.right);
        }
        int[] res = new int[s2.size()];
        for(int i = 0; i<res.length;i++){
            res[i]=s2.pop().val;
        }
        return res;

     }
}

发表于 2023-07-21 23:18:22 回复(0)
Java
一颗宏心头像 一颗宏心 
import java.util.*;

public class Solution {
    
    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postOrder(root,list);
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    
    public static void postOrder(TreeNode root,List<Integer> list){
        if(root != null){
            postOrder(root.left,list);
            postOrder(root.right,list);
            list.add(root.val);
        }
    }
}

发表于 2022-12-02 23:46:23 回复(0)
Java
dynamo1头像 dynamo1 
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
        // write code here
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<Integer>();
        traversal(root, list);

        return list.stream().mapToInt(i->i).toArray();
    }


    private void traversal(TreeNode root, List<Integer> list) {

        if (root.left != null) {
            traversal(root.left, list);
        }

        if (root.right != null) {
            traversal(root.right, list);
        }
        list.add(root.val);
    }
}

发表于 2022-11-04 07:45:49 回复(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)
Java
牛客用户007头像 牛客用户007 
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];

        ArrayList<Integer> list = new ArrayList();
        Stack<TreeNode> s = new Stack();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            list.add(node.val);
            if (node.left != null) {
                s.push(node.left);
            }
            if (node.right != null) {
                s.push(node.right);
            }
        }

        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i ++) {
            arr[i] = list.get(arr.length - i - 1);
        }

        return arr;
    }
}

发表于 2022-08-25 15:54:57 回复(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整型一维数组
     */

    private List<Integer> list = new ArrayList<>();
    private void reseveNode(TreeNode node) {
        TreeNode rNode = reserveList(node);
        TreeNode cur = rNode;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.right;
        }
        reserveList(rNode);
    }
    private TreeNode reserveList(TreeNode head) {
        TreeNode pre = null;
        TreeNode next = null;
        while (head != null) {
            next = head.right;
            head.right = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    //morris
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        TreeNode tmp = root;
        TreeNode pre = null;
        while (tmp != null) {
            if (tmp.left != null) {
                pre = tmp.left;
                while (pre.right != null && pre.right != tmp) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = tmp;
                    tmp = tmp.left;
                } else {
                    pre.right = null;
                    reseveNode(tmp.left);
                    tmp = tmp.right;
                }
            } else {
                tmp = tmp.right;
            }
        }
        reseveNode(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}

发表于 2022-08-18 11:22:58 回复(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> res = new ArrayList<>();
        TreeNode pre = null;
        Deque<TreeNode> q = new LinkedList<>();
        while (!q.isEmpty() || root != null) {
            // 一直往左走，直到当前节点的左子节点为空
            while (root != null) {
                q.push(root);
                // 访问当前节点的左子树
                root = root.left;
            }
            // 弹出栈顶元素
            TreeNode pop = q.peek();
            if (pop.right == null || pop.right == pre) {
                // 访问当前节点
                /*
                    访问当前节点的条件:
                        1、当前节点无右子树
                        2、当前节点的右子树已经被访问了
                */
                res.add(pop.val);
                q.pop();
            } else {
                // 访问当前节点的右子树
                root = pop.right;
            }
            pre = pop;
        }
        
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}


发表于 2022-08-07 15:05:07 回复(0)
Java
624huiguorou头像 624huiguorou
后序遍历，同理 

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> l = new ArrayList<>();
    
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        postorder(root);
        int[] r = new int[l.size()];
        for(int i = 0; i < l.size(); i++){
            r[i] = l.get(i);
        }
        return r;
    }
    
    public void postorder(TreeNode root){
        if(root != null){
            //LDR
            postorder(root.left);
            postorder(root.right);
            l.add(root.val);
        }
    }
}


发表于 2022-07-23 19:28:05 回复(0)
Java
paceccccc头像 paceccccc 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    ArrayList<Integer> list = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        if(root!=null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}


发表于 2022-07-20 19:38:19 回复(1)
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
        
        if (root == null) {
            return new int[0];
        }
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        list = TreeNode(root, list);
        int[] nums = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			nums[i] = list.get(i);
		}
		return nums;
    }

    private ArrayList<Integer> TreeNode (TreeNode root, ArrayList<Integer> list) {
        if (root.left != null) {
            list = TreeNode(root.left, list);
        }
        if (root.right != null) {
            list = TreeNode(root.right, list);
        }
        list.add(root.val);
        return list;
    }
}

发表于 2022-05-27 17:36:20 回复(0)
Java
牛客839384289号头像 牛客839384289号 
    ArrayList<Integer> postList = new ArrayList<>();
    
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        postOrder(root);
        return postList.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        postList.add(root.val);
    }

发表于 2022-05-14 13:40:36 回复(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
        if(root == null ) return new int[0];
        ArrayList<Integer> list =new ArrayList<Integer>();
        DoSearch(root,list);
        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size();i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
    public void DoSearch(TreeNode root,ArrayList list){
          if(root != null){
            DoSearch(root.left,list);
            DoSearch(root.right,list);
            list.add(root.val);
        }
            
        
    }
}

发表于 2022-05-04 22:20:41 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的后序遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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