二叉树的非递归后序遍历

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

![70][]

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

[70]: /images/20220523/d53bd475e59f40d2926aa33a132ef285.png