#yyds干货盘点# 面试必刷TOP101：二叉树的后序遍历

#yyds干货盘点# 面试必刷TOP101：二叉树的后序遍历

1.简述：

描述

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

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

样例图

示例1

输入：

{1,#,2,3}

返回值：

[3,2,1]

说明：

如题面图

示例2

输入：

{1}

返回值：

[1]

2.代码实现：

import java.util.*;public class Solution { public int[] postorderTraversal (TreeNode root) { //添加遍历结果的数组 List list = new ArrayList(); Stack s = new Stack(); TreeNode pre = null; while(root != null || !s.isEmpty()){ //每次先找到最左边的节点 while(root != null){ s.push(root); root = root.left; } //弹出栈顶 TreeNode node = s.pop(); //如果该元素的右边没有或是已经访问过 if(node.right == null || node.right == pre){ //访问中间的节点 list.add(node.val); //且记录为访问过了 pre = node; }else{ //该节点入栈 s.push(node); //先访问右边 root = node.right; } } //返回的结果 int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。