二叉树的先、中序非递归遍历 怼烎@ 2022-05-23 03:16 156阅读 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
还没有评论,来说两句吧...