// 第 14 周 – 实践课练习的参考答案
// 运行：java Exercises14.java
import java.util.ArrayList;
import java.util.List;

public class Exercises14 {

    static class Node {
        int value;
        Node left, right;
        Node(int v, Node l, Node r) { value = v; left = l; right = r; }
        Node(int v) { this(v, null, null); }
    }

    // E1. 元素的和与最大值
    static int sum(Node p) { return p == null ? 0 : p.value + sum(p.left) + sum(p.right); }

    static int max(Node p) {
        if (p == null) return Integer.MIN_VALUE;
        return Math.max(p.value, Math.max(max(p.left), max(p.right)));
    }

    // E2. 有多少个结点恰好有一个孩子？
    static int oneChild(Node p) {
        if (p == null) return 0;
        int self = ((p.left == null) != (p.right == null)) ? 1 : 0;
        return self + oneChild(p.left) + oneChild(p.right);
    }

    // E3. 是否是满（严格）二叉树？（每个结点都有 0 个或 2 个孩子）
    static boolean isFull(Node p) {
        if (p == null) return true;
        if ((p.left == null) != (p.right == null)) return false;
        return isFull(p.left) && isFull(p.right);
    }

    // E4. 第 k 层的元素
    static void level(Node p, int k, List<Integer> out) {
        if (p == null) return;
        if (k == 0) {
            out.add(p.value);
            return;
        }
        level(p.left, k - 1, out);
        level(p.right, k - 1, out);
    }

    // E5. 输出所有根–叶子路径
    static void paths(Node p, String prefix) {
        if (p == null) return;
        String s = prefix.isEmpty() ? "" + p.value : prefix + " -> " + p.value;
        if (p.left == null && p.right == null) System.out.println("    " + s);
        paths(p.left, s);
        paths(p.right, s);
    }

    // E6. 两棵树是否相同（结构和值都相同）？
    static boolean same(Node a, Node b) {
        if (a == null || b == null) return a == b;
        return a.value == b.value && same(a.left, b.left) && same(a.right, b.right);
    }

    public static void main(String[] args) {
        //        8
        //      /   \
        //     3     10
        //    / \      \
        //   1   6      14
        //      / \    /
        //     4   7  13
        Node t = new Node(8, new Node(3, new Node(1), new Node(6, new Node(4), new Node(7))),
                new Node(10, null, new Node(14, new Node(13), null)));
        System.out.println("E1. sum = " + sum(t) + ", maximum = " + max(t));
        System.out.println("E2. nodes with one child: " + oneChild(t));
        System.out.println("E3. full? " + isFull(t) + ", is the subtree of 3 full? " + isFull(t.left));
        List<Integer> l2 = new ArrayList<>();
        level(t, 2, l2);
        System.out.println("E4. level 2: " + l2);
        System.out.println("E5. root–leaf paths:");
        paths(t, "");
        Node copy = new Node(8, new Node(3, new Node(1), new Node(6, new Node(4), new Node(7))),
                new Node(10, null, new Node(14, new Node(13), null)));
        System.out.println("E6. same(t, copy) = " + same(t, copy) + ", same(t, t.left) = " + same(t, t.left));
    }
}