datastructures7BinaryTree

1package pkg3datastructures;2 3/*4 * datastructures7BinaryTree.java5 * ---------------6 * A binary tree with the four traversals (pre/in/post-order DFS and7 * level-order BFS), height, and node count.8 *9 * COMPLEXITY: each traversal O(n); height O(n).10 * NOTE: a plain binary tree has no ordering rule (unlike a BST).11 */12import java.util.*;13 14public class datastructures7BinaryTree {15 16    static class Node {17        int val; Node left, right;18        Node(int val) { this.val = val; }19    }20 21    static void preorder(Node n, List<Integer> out)  { if (n == null) return; out.add(n.val); preorder(n.left, out); preorder(n.right, out); }22    static void inorder(Node n, List<Integer> out)   { if (n == null) return; inorder(n.left, out); out.add(n.val); inorder(n.right, out); }23    static void postorder(Node n, List<Integer> out) { if (n == null) return; postorder(n.left, out); postorder(n.right, out); out.add(n.val); }24 25    static List<List<Integer>> levelOrder(Node root) {26        List<List<Integer>> levels = new ArrayList<>();27        if (root == null) return levels;28        Queue<Node> q = new LinkedList<>();29        q.offer(root);30        while (!q.isEmpty()) {31            int n = q.size();32            List<Integer> level = new ArrayList<>();33            for (int i = 0; i < n; i++) {34                Node cur = q.poll();35                level.add(cur.val);36                if (cur.left != null) q.offer(cur.left);37                if (cur.right != null) q.offer(cur.right);38            }39            levels.add(level);40        }41        return levels;42    }43 44    static int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }45    static int count(Node n)  { return n == null ? 0 : 1 + count(n.left) + count(n.right); }46 47    public static void main(String[] args) {48        //        149        //       / \50        //      2   351        //     / \   \52        //    4   5   653        Node root = new Node(1);54        root.left = new Node(2); root.right = new Node(3);55        root.left.left = new Node(4); root.left.right = new Node(5);56        root.right.right = new Node(6);57 58        List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();59        preorder(root, pre); inorder(root, in); postorder(root, post);60        System.out.println("preorder:  " + pre);61        System.out.println("inorder:   " + in);62        System.out.println("postorder: " + post);63        System.out.println("levelOrder: " + levelOrder(root));64        System.out.println("height=" + height(root) + " count=" + count(root));65    }66}