二叉树的先、中序非递归遍历-蒲公英云

二叉树的先、中序非递归遍历

怼烎@ 2022-05-23 03:16 270阅读 0赞

这里写图片描述

import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
 }
public class Solution {
    //二叉树非递归前序遍历
    public ArrayList<Integer> preorderTraversal(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(node.val);
             if(node.right!=null)
             {
                 stack.push(node.right);
             }
             if(node.left!=null)
             {
                 stack.push(node.left);
             }
        }
        return list;
    }
    //二叉树非递归中序序遍历
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer>list=new ArrayList<>();
        Stack<TreeNode>stack=new Stack<>();
        if(root==null)
            return list;
        TreeNode node=root;
        while(node!=null||stack.size()>0){
             //把当前节点的所有左子节点压入栈
             while(node!=null)
             {
                 stack.push(node);
                 node=node.left;
             }
             //访问节点处理右节点
             while(stack.size()>0){
                 node=stack.pop();
                 list.add(node.val);
                 node=node.right;
             }
        }
        return list;
    }
    public static void main(String[]args){
       // System.out.println("Hello");
        TreeNode node=new TreeNode(1);
        node.left=new TreeNode(2);
        node.right=new TreeNode(3);
        node.right.left=new TreeNode(4);
        node.right.right=new TreeNode(5);
        Solution s=new Solution();
        ArrayList<Integer>list=s.inorderTraversal(node);
        for(int k:list)
        {
             System.out.print(k+" ");
        }
    }
}