用递归的方法对给定的二叉树进行后序遍历。
例如：
给定的二叉树为{1,#,2,3},
返回[3,2,1].
[编程题]二叉树的后序遍历
// 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
// 如果P不存在左孩子和右孩子，则可以直接访问它；
// 或者P存在孩子，但是其孩子都已被访问过了，则同样可以直接访问该结点
// 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了
// 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
public static ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if(root == null)
return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
stack.push(root);
while(!stack.isEmpty()){
// 只看栈顶元素，不弹出
TreeNode cur = stack.peek();
if((cur.left == null && cur.right == null)
|| (pre != null && (pre == cur.left || pre == cur.right))){
list.add(cur.val);
stack.pop();
pre = cur;
}
else{
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
return list;
}
发表于 2017-05-08 15:01:26
回复(14)
/* 这个解法可能是最佳实践，思路清晰，易于理解。
* 核心思想是用栈做辅助空间，先从根往左一直入栈，直到为空，然后判断栈顶元素的右孩子，如果不为空且未被访问过，
* 则从它开始重复左孩子入栈的过程；否则说明此时栈顶为要访问的节点（因为左右孩子都是要么为空要么已访问过了），
* 出栈然后访问即可，接下来再判断栈顶元素的右孩子...直到栈空。
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
TreeNode p = root, r = null; //P记录当前节点，r用来记录上一次访问的节点
Stack<TreeNode> s = new Stack<TreeNode>();
ArrayList<Integer> list = new ArrayList<Integer>();
while(p != null || !s.isEmpty()) {
if(p != null) { //左孩子一直入栈，直到左孩子为空
s.push(p);
p = p.left;
} else {
p = s.peek();
p = p.right;
if(p != null && p != r) { //如果栈顶元素的右孩子不为空，且未被访问过
s.push(p); //则右孩子进栈，然后重复左孩子一直进栈直到为空的过程
p = p.left;
} else {
p = s.pop(); //否则出栈，访问，r记录刚刚访问的节点
list.add(p.val);
r = p;
p = null;
}
}
}
return list;
}
}
发表于 2016-11-13 20:45:36
回复(11)
/**
*不使用递归解答，这才是最简单而且高效的方法吧。
*从后往前观察后序遍历后的结果就明白思路了。
*/
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return list;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(0, node.val);//每次插入到头部
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);
}
return list;
}
编辑于 2017-04-28 15:33:52
回复(11)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//=====================递归=================================
class Solution {
public:
void postOrder(TreeNode *root,vector<int>&vec){
if(root != NULL){
postOrder(root->left,vec);
postOrder(root->right,vec);
vec.push_back(root->val);
}
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int>vec;
postOrder(root,vec);
return vec;
}
};
//=====================非递归============================
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int>vec;
if(root == NULL)
return vec;
stack<TreeNode*>st;
st.push(root);
TreeNode * cur = NULL;
while(!st.empty()){
cur = st.top();
if(cur->left == NULL && cur->right == NULL){
vec.push_back(cur->val);
st.pop();
}else{
if(cur->right){
st.push(cur->right);
cur->right = NULL;
}
if(cur->left){
st.push(cur->left);
cur->left = NULL;
}
}
}
return vec;
}
};
发表于 2016-04-05 21:28:32
回复(5)
import java.util.*;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || ! stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.peek();
if(root.right == null || root.right == pre) {
list.add(stack.pop().val);
pre = root;
root = null;
} else root = root.right;
}
return list;
}
}
发表于 2017-03-12 16:53:26
回复(0)
//思路：用栈来实现，顶点先入栈，向左到最左下角，保存路径，右不为空，右进站继续左
//当左右子树都为空时，访问，弹栈，并将pre到p的指针为0，避免下次再访问该路径。
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
vector<TreeNode *> s;
if (!root)
return res;
s.push_back(root);
TreeNode* p = nullptr;
while (!s.empty()){
p = s.back();
while (p->left){
s.push_back(p->left);
p = p->left;
}
if (p->right == nullptr){
res.push_back(p->val);
s.pop_back();
if(s.empty()) break;//一定要判断
TreeNode *pre = s.back();
if (p == pre->left)
pre->left = nullptr;
if (p == pre->right)
pre->right = nullptr;
}
else
s.push_back(p->right);
}
return res;
}
};
发表于 2016-08-20 23:12:18
回复(1)
import java.util.*;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root==null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode r = stack.pop();
if(r.left!=null)
stack.add(r.left);
if(r.right!=null)
stack.add(r.right);
stack2.add(r);
}
while(!stack2.isEmpty()){
list.add(stack2.pop().val);
}
//LRD(list,root);递归
return list;
}
public void LRD(ArrayList<Integer> list,TreeNode root){
if(root==null)
return;
LRD(list,root.left);
LRD(list,root.right);
list.add(root.val);
}
}
发表于 2016-05-30 16:11:12
回复(1)
import java.util.ArrayList;
public class Solution {
public ArrayList<integer> postorderTraversal(TreeNode root) {
if (root != null) {
ArrayList<integer> l = postorderTraversal(root.left);
ArrayList<integer> r = postorderTraversal(root.right);
ArrayList<integer> res = new ArrayList<>();
res.addAll(l);
res.addAll(r);
res.add(root.val);
return res;
}
return new ArrayList<>();
}
}
</integer></integer></integer></integer>
发表于 2019-01-21 11:14:07
回复(0)
题目描述
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
解题思路
就是二叉树的后序遍历，它的意思是，递归程序没啥意思，要不你用非递归来实现一个？
我们知道，递归就是系统栈实现的，那么其实对于本题，我倾向于自己用一个栈来模拟系统栈，这样，无论是前序中序还是后序，改代码跟递归版本是一样，具有较强的通用性，至于另外的解法，每种都不一样，导致不好记忆。
代码提交
import java.util.*;
class Command{
public String str;
public TreeNode node;
public Command(String str,TreeNode node){
this.str = str;
this.node = node;
}
}
public class Solution {
public ArrayList postorderTraversal(TreeNode root) {
ArrayList res = new ArrayList();
if(root == null){
return res;
}
Stack stack = new Stack();
//遇到“go”则添加左右孩子以及自己入栈
//遇到“print”则添加进结果集
stack.push(new Command("go",root));
while(!stack.isEmpty()){
Command c = stack.pop();
if(c.str == "go"){
//先自己
stack.push(new Command("print",c.node));
//再右
if(c.node.right != null){
stack.push(new Command("go",c.node.right));
}
//再左
if(c.node.left != null){
stack.push(new Command("go",c.node.left));
}
//出栈的顺序必然是左-右-中，即后序遍历顺序
}else{
res.add(c.node.val);
}
}
return res;
}
}我们要想改成前序或者中序遍历，只需要将stack.push(new Command("print",c.node));调换一下位置即可，十分方便，这样对递归的实现原理的理解也加深了。
编辑于 2019-03-23 20:45:43
回复(0)
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if(root == null) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root , lastVisitNode = null;
while(cur != null){
stack.add(cur);
cur = cur.left;
}
while(!stack.empty()){
cur = stack.peek();
if(cur.right == null || cur.right == lastVisitNode){
//当右侧节点为空 或者为访问过的节点的时候
stack.pop();
ret.add(cur.val);
lastVisitNode = cur;
}
else{ //节点不为空 且 上次访问的是左树
cur = cur.right;
while(cur != null){
stack.add(cur);
cur = cur.left;
}
}
}
return ret;
}
编辑于 2017-12-18 16:58:45
回复(0)
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
if(root == NULL)
return result;
stack<TreeNode *> s;
s.push(root);
while(!s.empty())
{
TreeNode *p = s.top();
s.pop();
result.push_back(p->val);
if(p->left != NULL)
s.push(p->left);
if(p->right != NULL)
s.push(p->right);
}
reverse(result.begin(), result.end());
return result;
}
};
发表于 2017-08-21 01:30:57
回复(0)
//大家好，我是yishuihan
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> vec;
if(root==NULL) return vec;
helper(vec,root);
return vec;
}
void helper(vector<int>& vec,TreeNode* root)
{
if(root==NULL) return;
helper(vec,root->left);
helper(vec,root->right);
vec.push_back(root->val);
}
};
发表于 2016-08-06 20:22:24
回复(0)
import java.util.ArrayList;
public class Solution {
// 后序遍历：左 右 中
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
return list;
}
}
发表于 2017-03-10 16:09:03
回复(3)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ans;
if (root == NULL) return ans;
vector<TreeNode*> vec;
vec.push_back(root);
while (vec.size() > 0) {
int tail = vec.size() - 1;
if (vec[tail]->left == NULL && vec[tail]->right == NULL) {
ans.push_back(vec[tail]->val);
vec.pop_back();
}
if (vec[tail]->right != NULL) {
vec.push_back(vec[tail]->right);
vec[tail]->right = NULL;
}
if (vec[tail]->left != NULL) {
vec.push_back(vec[tail]->left);
vec[tail]->left = NULL;
}
}
return ans;
}
};
发表于 2020-07-11 14:28:19
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector
*/
vector<int> postorderTraversal(TreeNode* root) {
// write code here
vector<int> ans;
if(!root) return ans;
stack<TreeNode*> buffer;
buffer.push(root);
while(!buffer.empty()){
auto *cur = buffer.top();
if(!cur->left && !cur->right) ans.emplace_back(cur->val), buffer.pop();
else{
if(cur->right) buffer.push(cur->right), cur->right = nullptr;
if(cur->left) buffer.push(cur->left), cur->left = nullptr;
}
}
return ans;
}
};
发表于 2020-07-07 09:03:09
回复(2)
我这里用一个简单的模板讲清楚前序后序中序遍历的全部迭代模型。
后续遍历和中序遍历都可以是基于前序遍历的模板。
所以先学前序遍历，学好前序遍历，其他的一句或三句话就可以了。
我们开始吧·~~~
1.前序遍历：
1.定义一个辅助栈
2.根节点先入栈
3.左节点入栈
4.栈顶左节点出栈。下一次while内循环的时候左节点的右子树入栈。
vector<int> preorderTraversal(TreeNode *root){
vector<int> res;
if(!root) return res;
stack<TreeNode*> stk;
while(stk.size() > 0 || root != nullptr){
while(root){
//根节点入栈
stk.push(root);
res.push_back(root->val);
//左节点入栈
root = root->left;
}
//保存当前栈顶的right节点。下一次进入第二层又循环的时候入站（相当于右接待你入栈）
root = stk.top()->right;
//左节点出站
stk.pop();
}
return res;
}
2.后序遍历
后续遍历和前序遍历一样，区别就是root->left->right的顺序变成了root->right->left 最后执行一次reverse。就变成了left->right->root.
vector<int> postorderTraverse(TreeNode* root){
vector<int> res;
if(!root) return res;
stack<TreeNode*> stk;
while(stk.size() > 0 || !root){
while(root){
stk.push(root);
res.push_back(root->val);
//和前序遍历的区别1
root = root->right;
}
//和前序遍历的区别2
root = stk.top()->left;
stk.pop();
}
//和前序遍历的区别3.
reverse(res.begin(), res.end());
return res;
} 3.中序
中序遍历也差不多。
就是顺序变成了left->root->right
和前序遍历的唯一区别就是：res.push_back()不是在遍历根节点的时候和stk一起push。
而是在出栈之前push。
vector<int> inorderTraverse(TreeNode* root){
vector<int> res;
if(!root) return root;
stack<TreeNode* > stk;
while(stk.size()>0 || !root){
while(root){
stk.push(root);
root = root->left;
}
res.push_back(stk.top()-> val);
//和前序遍历的唯一区别
root = stk.top()->right;
stk.pop();
}
return res;
} 所以，这个模板你学会了吗？
如果没看懂，请多看几次前序遍历。
觉得好的话，给我点个赞。
发表于 2020-03-28 10:39:41
回复(0)
这里使用一个set来记录访问过的节点来判断子节点是否访问过，因为HashSet支持null值，所以空值也可以判断。
import java.util.*;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> set = new HashSet<>();
set.add(root);
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(set.contains(node.left) && set.contains(node.right)){
list.add(node.val);
continue;
}
set.add(node.right);
set.add(node.left);
stack.push(node);
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return list;
}
}
编辑于 2019-12-30 14:32:37
回复(0)
/** 采用 根——右——左 的顺序进行遍历，利用栈实现
遍历过程中将元素值添加到指定ArrayList中
最后将列表翻转即可，间接实现对 左——右——根 的访问
*/
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<TreeNode>();
ArrayList<Integer> list=new ArrayList<Integer>();
if(root!=null){
stack.push(root);
while(stack!=null && stack.size()!=0){
TreeNode p=stack.pop();
list.add(p.val);
if(p.left!=null){
stack.push(p.left);
}
if(p.right!=null){
stack.push(p.right);
}
}
Collections.reverse(list);
}
return list;
}
}
发表于 2019-11-21 10:48:40
回复(0)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
if (root==nullptr)
return res;
stack<TreeNode*> s;
s.push(root);
map<TreeNode*,int> flag;
while (!s.empty())
{
TreeNode *temp = s.top();
if (flag[temp]==1)
{
res.push_back(temp->val);
s.pop();
continue;
}
if (temp->right!=nullptr || temp->left!=nullptr)
{
if (temp->right!=nullptr)
{
s.push(temp->right);
flag[temp] = 1;
}
if (temp->left!=nullptr)
{
s.push(temp->left);
flag[temp] = 1;
}
}
else{
res.push_back(temp->val);
s.pop();
}
}
return res;
}
private:
vector<int> res;
};
结合map判断节点是否被访问过
发表于 2019-09-01 16:54:30
回复(0)
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if(root==nullptr)
return res;
stack<TreeNode *> stackNode;
TreeNode * leftNode=root;
while(leftNode!=nullptr)
{
stackNode.push(leftNode);
TreeNode * temp=leftNode;
leftNode=leftNode->left;
temp->left=nullptr;
}
while(!stackNode.empty())
{
TreeNode *p=stackNode.top();
if(p->right!=nullptr)
{
TreeNode * q=p->right;
p->right=nullptr;
while(q!=nullptr)
{
stackNode.push(q);
TreeNode * temp=q;
q=q->left;
temp->left=nullptr;
}
}else{
res.push_back(p->val);
stackNode.pop();
}
}
return res;
}
};
发表于 2019-08-13 12:34:41
回复(0)
问题信息
难度：
231条回答
251收藏
30903浏览
通过挑战的用户
查看代码-
2022-12-28 13:55:21 -
2022-09-16 18:51:18 -
2022-09-14 00:41:45
-
2022-09-13 18:50:30 -
2022-09-13 17:46:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
