二叉树的后序遍历

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;
public class Solution {
    
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(root==null)
            return list;
        function(list,root);
        return list;
    }
    public void function(ArrayList<Integer> list,TreeNode root){
        if(root==null)
            return;
        if(root.left!=null){
            function(list,root.left);
        }
        if(root.right!=null){
            function(list,root.right);
        }
        list.add(root.val);
    }
}

/** 采用 根——右——左 的顺序进行遍历，利用栈实现
    遍历过程中将元素值添加到指定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;
    }
}

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
         ArrayList<Integer> list = new ArrayList<Integer>();
         //非递归实现
          if(root!=null){
              Stack<TreeNode> s1=new Stack<>();
              Stack<TreeNode> s2=new Stack<>();
              s1.push(root);
              while(!s1.isEmpty()){
                  root=s1.pop();
                  s2.push(root);
                  if (root.left != null) {                     s1.push(root.left);                 }                 if (root.right != null) {                     s1.push(root.right);                 }             }               while (!s2.isEmpty()) {                 list.add(s2.pop().val);             }
              }
        return list;
        
          }
    
}

题目描述

Given a binary tree, return the postorder traversal of its nodes' values.

For example:

Given binary tree{1,#,2,3},

1
    \
     2
    /
   3

return[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));调换一下位置即可，十分方便，这样对递归的实现原理的理解也加深了。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
   public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        Stack<Integer> sval = new Stack<Integer>();
        while(root!=null || !s.isEmpty()){
            while(root!=null){
                s.push(root.left);
                sval.push(root.val);
                root = root.right;
            }
            root = s.pop();
        }
        while(!sval.isEmpty())
            list.add(sval.pop());
        return list;
    }

}
如果明白了上面压栈的做法，那么稍微改一下，就更简洁了

public ArrayList<Integer> postorderTraversal(TreeNode root) {
      ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        while(root!=null || !s.isEmpty()){
            while(root!=null){
                s.push(root.left);
                list.add(0, root.val);
                root = root.right;
            }
            root = s.pop();
        }
        return list;
    }

import java.util.*;//递归比较省心
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        if(root==null)return al;
        al.addAll(postorderTraversal(root.left));
        al.addAll(postorderTraversal(root.right));
        al.add(root.val);
        return al;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if(root == null)
            return result;
        // nStack 存放树节点
        Stack<TreeNode> nStack = new Stack<>();
        // iStack 为存放状态的辅助栈，label表示nStack栈顶结点的状态。
        // state = 0 时，表示该节点左右结点都没有遍历过
        // state = 1 时，表示该结点左结点遍历过，右结点没有遍历过
        // state = 2 时，表示该结点左右结点都遍历过
        Stack<Integer> iStack = new Stack<>();
        // 首先压入根节点
        nStack.push(root);
        // 此处压入的0为占位符
        iStack.push(0);
        // label 标注此时nStack栈顶结点的状态
        int label = 0;
        while(!nStack.isEmpty()){
            // 获取栈顶结点
            TreeNode node = nStack.peek();
            // 根据状态标签判断如何处理该结点
            if(label == 2 || (label == 1 && node.right == null) || (node.left == null && node.right == null)){
                // 栈顶弹出后，需要从状态位辅助栈获取最新标签
                label = iStack.pop();
                result.add(nStack.pop().val);
            }else if(label == 0 && node.left != null){
                iStack.push(1);
                nStack.push(node.left);
                // 当压入新节点后，nStack栈顶改变，所以要改变此时的状态标签，label = 0
                label = 0;
            }else if(label == 0 && node.left == null){
                iStack.push(2);
                nStack.push(node.right);
                label = 0;
            }else if(label == 1){
                iStack.push(2);
                nStack.push(node.right);
                label = 0;
            }
            
        }
        return result;
    }
}

public ArrayList postOrderTraversalByIterative(TreeNode root) {
    ArrayList returnList = new ArrayList(); if (root == null) { return returnList;
    }
    Stack stack = new Stack();
    stack.push(root); 
    // 当前节点  
    TreeNode pCur; 
    // 上一个访问的节点  
    TreeNode preNode = null; 
    while (!stack.empty()) {
        pCur = stack.lastElement(); if ((pCur.left == null && pCur.right == null)
                || (preNode != null && (pCur.right == preNode || pCur.left == preNode))) {
            returnList.add(pCur.val);
            preNode = pCur;
            stack.pop();
        } else { if (pCur.right != null) {
                stack.push(pCur.right);
            } if (pCur.left != null) {
                stack.push(pCur.left);
            }
        }
    } return returnList;
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
        return new ArrayList<>();
    }
    ArrayList<Integer> list = new ArrayList<>();
    list.addAll(postorderTraversal(root.left));
    list.addAll(postorderTraversal(root.right));
    list.add(root.val);
    return list;
    }
}

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
       ArrayList<Integer> postOrderList = new ArrayList<Integer>();
        if(root == null) return postOrderList;
        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();

        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);
        }

        while (!stack2.isEmpty()){
            TreeNode node = stack2.pop();
            postOrderList.add(node.val);
        }
        return postOrderList; 
    }
}

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;
    }

//后序遍历,递归解法
import java.util.*;

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        if(root == null){
            return resultList;
        }
        getResult(root,resultList);
        return resultList;
    }
    
    public void getResult(TreeNode root , ArrayList<Integer> resultList){
        if(root.left != null){
            getResult(root.left,resultList);
        }
        if(root.right != null){
            getResult(root.right,resultList);
        }
        resultList.add(root.val);
    }
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}