给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围：二叉树的节点数量满足 
，二叉树节点的值满足 
，树的各节点的值各不相同
样例图
[编程题]二叉树的后序遍历
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)
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)
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)
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)
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)
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)
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)
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)
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)
迭代版后序遍历
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)
后序遍历，同理
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)
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)
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)
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)
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)
问题信息
难度：
23条回答
211收藏
3668浏览
通过挑战的用户
查看代码-
2023-02-28 11:58:26
-
2022-09-17 00:58:47 -
2022-09-16 19:18:45
-
2022-09-16 17:11:34 -
2022-09-16 16:28:31
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
