二叉树的层序遍历--Java实现

ゝ一纸荒年。 2023-01-21 05:22 106阅读 0赞

package org.simpleframework.leetcode;
    
    import java.util.*;
    
    /** * @author mazhen * @className LevelTraversal * @Description 层序遍历: https://blog.csdn.net/weixin_43548025/article/details/106460961 * @date 2021/5/13 11:13 */
    public class LevelTraversal { 
        public static void main(String[] args) { 
    
            ListNode node4 = new ListNode(4,null,null);
            ListNode node5 = new ListNode(5,null,null);
            ListNode node3 = new ListNode(3,node4,node5);
            ListNode node2 = new ListNode(2,null,null);
            ListNode node1 = new ListNode(1,node2,node3);
            //printNode(node1);
            printBootNode(node1);
    
        }
    
        //给定一个二叉树，返回该二叉树由顶层到底层的层序遍历，（从左向右，从根节点到叶子节点，一层一层的遍历）
        public static void printNode(ListNode root) { 
            if (root == null) { 
                return;
            }
            Queue<ListNode> queue = new LinkedList<>();
            queue.add(root);
            while (queue.size()>0) { 
                ListNode node = queue.poll();
                if (node == null) { 
                   return;
                }
                System.out.println(node.value);
                if (node.left != null) { 
                    queue.add(node.left);
                }
                if (node.right != null) { 
                    queue.add(node.right);
                }
    
            }
        }
    
        //给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）
        public static void printBootNode(ListNode root) { 
            if (root == null) { 
                return;
            }
            Stack<Integer> stack = new Stack<>();
            Queue<ListNode> queue = new LinkedList<>();
            queue.add(root);
            while (queue.size()>0) { 
                ListNode node = queue.poll();
                if (node == null) { 
                    break;
                }
                stack.push(node.value);
                if (node.right != null) { 
                    queue.add(node.right);
                }
                if (node.left != null) { 
                    queue.add(node.left);
                }
            }
            while (!stack.empty()) { 
                System.out.println(stack.pop());
            }
        }
    
        public static class ListNode { 
            private final int value;
            private final ListNode left;
            private final ListNode right;
    
            public ListNode(int value,ListNode left,ListNode right) { 
                this.value = value;
                this.left = left;
                this.right = right;
            }
        }
    
    }