二叉树的非递归后序遍历-蒲公英云

二叉树的非递归后序遍历

小灰灰 2022-05-23 02:59 261阅读 0赞

import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //解法一:双栈实现二叉树的非递归后序遍历 
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
         ArrayList<Integer> list=new ArrayList<>();
         if(root==null)
             return list;
         Stack<TreeNode>stack=new Stack<>();//存储节点
         Stack<TreeNode>temp=new Stack<>();//存储节点
         TreeNode node=root;
         while(node!=null||stack.size()>0){
             //把当前节点及其右侧节点压入栈
            while(node!=null){
                stack.push(node);
                temp.push(node);
                node=node.right;
            }
            //处理栈顶的左侧节点
            if(stack.size()>0){
                node=stack.pop();
                node=node.left;
            }
         }
         while(!temp.isEmpty()){
            list.add(temp.pop().val);
         }
         return list;
    }
    //方法二:单栈遍历法
     public ArrayList<Integer> postorderTraversal2(TreeNode root) {
        ArrayList<Integer> list=new ArrayList<>();
         if(root==null)
             return list;
        Stack<TreeNode>stack=new Stack<>();//存储节点
        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;
     }
    public static void main(String[]args){ //System.out.println("Hello World!"); } }