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

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

![这里写图片描述][70]

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

![这里写图片描述][70 1]

[70]: /images/20220523/f7afd13c474f47509cac37ee438d4aef.png
[70 1]: /images/20220523/7b84b95210c4431987ae290ed1973b82.png