题解 | #二叉搜索树的后序遍历序列#

package com.yzcOfffer.JZ77;


import java.util.ArrayList;
import java.util.Stack;

/**
 * @author YZC
 * @date 2021/12/5 20:56
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
 public  class Solution {

     public static void main(String[] args) {
         TreeNode node1 = new TreeNode(1);
         TreeNode node2 = new TreeNode(2);
         TreeNode node3 = new TreeNode(3);
         TreeNode node4 = new TreeNode(4);
         TreeNode node5 = new TreeNode(5);
         node1.left = node2;
         node1.right = node3;
         node3.left = node4;
         node3.right = node5;
         System.out.println(Print(node1));
     }


     public static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
         //之字形顺序打印二叉树
         ArrayList<ArrayList<Integer>> res=new ArrayList<>();
         if(pRoot==null)
             return res;
         Stack<TreeNode> stack1=new Stack<>();
         Stack<TreeNode> stack2=new Stack<>();
         stack1.push(pRoot);
         while(!stack1.isEmpty() || !stack2.isEmpty()){
             ArrayList<Integer> list=new ArrayList<>();
             if(!stack1.isEmpty()){
                 while(!stack1.isEmpty()){
                     TreeNode temp=stack1.pop();
                     list.add(temp.val);
                     if(temp.left!=null)  //先左后右
                         stack2.push(temp.left);
                     if(temp.right!=null)
                         stack2.push(temp.right);
                 }
             }else{
                 while(!stack2.isEmpty()){
                     TreeNode temp=stack2.pop();
                     list.add(temp.val);
                     if(temp.right!=null)   //先右后左
                         stack1.push(temp.right);
                     if(temp.left!=null)
                         stack1.push(temp.left);
                 }
             }
             res.add(list);
         }
         return res;
     }
 }