Duyệt Tiền Thứ Tự

class GiảiPháp {
    void duyetTruoc(Đỉnh gốc, List<Integer> kq) {
        if (gốc == null) return;
        kq.add(gốc.val);
        duyetTruoc(gốc.trái, kq);
        duyetTruoc(gốc.phải, kq);
    }
    
    public List<Integer> duyetTienTu(Đỉnh gốc) {
        List<Integer> kq = new ArrayList<>();
        duyetTruoc(gốc, kq);
        return kq;
    }
}

Duyệt Hậu Thứ Tự

class GiảiPháp {
    void duyetSau(Đỉnh gốc, List<Integer> kq) {
        if (gốc == null) return;
        duyetSau(gốc.trái, kq);
        duyetSau(gốc.phải, kq);
        kq.add(gốc.val);
    }
    
    public List<Integer> duyetHauTu(Đỉnh gốc) {
        List<Integer> kq = new ArrayList<>();
        duyetSau(gốc, kq);
        return kq;
    }
}

Duyệt Trung Thứ Tự

class GiảiPháp {
    void duyetGiua(Đỉnh gốc, List<Integer> kq) {
        if (gốc == null) return;
        duyetGiua(gốc.trái, kq);
        kq.add(gốc.val);
        duyetGiua(gốc.phải, kq);
    }
    
    public List<Integer> duyetTrungTu(Đỉnh gốc) {
        List<Integer> kq = new ArrayList<>();
        duyetGiua(gốc, kq);
        return kq;
    }
}

Duyệt Theo Tầng

class GiảiPháp {
    public List<List<Integer>> duyetTheoTang(Đỉnh gốc) {
        List<List<Integer>> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int soLuong = hangDoi.size();
            List<Integer> tang = new ArrayList<>();
            
            for (int i = 0; i < soLuong; i++) {
                Đỉnh nut = hangDoi.poll();
                tang.add(nut.val);
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
            kq.add(tang);
        }
        return kq;
    }
}

Duyệt Tầng Ngược

class GiảiPháp {
    public List<List<Integer>> duyetNguoc(Đỉnh gốc) {
        List<List<Integer>> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int kichThuoc = hangDoi.size();
            List<Integer> tang = new ArrayList<>();
            
            for (int i = 0; i < kichThuoc; i++) {
                Đỉnh nut = hangDoi.poll();
                tang.add(nut.val);
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
            kq.add(0, tang);
        }
        return kq;
    }
}

Góc Nhìn Bên Phải

class GiảiPháp {
    public List<Integer> nhinBenPhai(Đỉnh gốc) {
        List<Integer> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int soNut = hangDoi.size();
            for (int i = 0; i < soNut; i++) {
                Đỉnh nut = hangDoi.poll();
                if (i == soNut - 1) kq.add(nut.val);
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
        }
        return kq;
    }
}

Trung Bình Mỗi Tầng

class GiảiPháp {
    public List<Double> trungBinhTang(Đỉnh gốc) {
        List<Double> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int soLuong = hangDoi.size();
            long tong = 0;
            
            for (int i = 0; i < soLuong; i++) {
                Đỉnh nut = hangDoi.poll();
                tong += nut.val;
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
            kq.add(tong * 1.0 / soLuong);
        }
        return kq;
    }
}

Duyệt Tầng Cây N-nhị

class GiảiPháp {
    public List<List<Integer>> duyetTangCayNhiPhan(Node gốc) {
        List<List<Integer>> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Node> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int kichThuoc = hangDoi.size();
            List<Integer> tang = new ArrayList<>();
            
            for (int i = 0; i < kichThuoc; i++) {
                Node nut = hangDoi.poll();
                tang.add(nut.val);
                for (Node con : nut.con) {
                    hangDoi.offer(con);
                }
            }
            kq.add(tang);
        }
        return kq;
    }
}

Giá Trị Lớn Nhất Mỗi Tầng

class GiảiPháp {
    public List<Integer> giaTriLonNhat(Đỉnh gốc) {
        List<Integer> kq = new ArrayList<>();
        if (gốc == null) return kq;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int soLuong = hangDoi.size();
            int max = Integer.MIN_VALUE;
            
            for (int i = 0; i < soLuong; i++) {
                Đỉnh nut = hangDoi.poll();
                max = Math.max(max, nut.val);
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
            kq.add(max);
        }
        return kq;
    }
}

Kết Nối Node Kế Tiếp

class GiảiPháp {
    public Node ketNoiNodeKeTiep(Node gốc) {
        if (gốc == null) return null;
        
        Queue<Node> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        
        while (!hangDoi.isEmpty()) {
            int soLuong = hangDoi.size();
            Node nutTruoc = null;
            
            for (int i = 0; i < soLuong; i++) {
                Node nutHienTai = hangDoi.poll();
                if (nutTruoc != null) nutTruoc.next = nutHienTai;
                nutTruoc = nutHienTai;
                
                if (nutHienTai.trái != null) hangDoi.offer(nutHienTai.trái);
                if (nutHienTai.phải != null) hangDoi.offer(nutHienTai.phải);
            }
        }
        return gốc;
    }
}

Độ Sâu Tối Đa

class GiảiPháp {
    public int doSauToiDa(Đỉnh gốc) {
        if (gốc == null) return 0;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        int doSau = 0;
        
        while (!hangDoi.isEmpty()) {
            int kichThuoc = hangDoi.size();
            doSau++;
            
            for (int i = 0; i < kichThuoc; i++) {
                Đỉnh nut = hangDoi.poll();
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
        }
        return doSau;
    }
}

Độ Sâu Tối Thiểu

class GiảiPháp {
    public int doSauToiThieu(Đỉnh gốc) {
        if (gốc == null) return 0;
        
        Queue<Đỉnh> hangDoi = new LinkedList<>();
        hangDoi.offer(gốc);
        int doSau = 0;
        
        while (!hangDoi.isEmpty()) {
            doSau++;
            int soLuong = hangDoi.size();
            
            for (int i = 0; i < soLuong; i++) {
                Đỉnh nut = hangDoi.poll();
                if (nut.trái == null && nut.phải == null) return doSau;
                if (nut.trái != null) hangDoi.offer(nut.trái);
                if (nut.phải != null) hangDoi.offer(nut.phải);
            }
        }
        return doSau;
    }
}

Đảo Ngược Cây Nhị Phân

class GiảiPháp {
    public Đỉnh daoNguocCay(Đỉnh gốc) {
        if (gốc == null) return null;
        
        Đỉnh trai = daoNguocCay(gốc.trái);
        Đỉnh phai = daoNguocCay(gốc.phải);
        
        gốc.trái = phai;
        gốc.phải = trai;
        return gốc;
    }
}

Kiểm Tra Đối Xứng

class GiảiPháp {
    public boolean kiemTraDoiXung(Đỉnh gốc) {
        if (gốc == null) return true;
        return soSanh(gốc.trái, gốc.phải);
    }
    
    private boolean soSanh(Đỉnh trai, Đỉnh phai) {
        if (trai == null && phai == null) return true;
        if (trai == null || phai == null) return false;
        return trai.val == phai.val 
            && soSanh(trai.trái, phai.phải) 
            && soSanh(trai.phải, phai.trái);
    }
}

Đếm Node Cây Hoàn Chỉnh

class GiảiPháp {
    public int demNode(Đỉnh gốc) {
        if (gốc == null) return 0;
        return 1 + demNode(gốc.trái) + demNode(gốc.phải);
    }
}

Kiểm Tra Cây Cân Bằng

class GiảiPháp {
    public boolean kiemTraCanBang(Đỉnh gốc) {
        return tinhDoSau(gốc) != -1;
    }
    
    private int tinhDoSau(Đỉnh nut) {
        if (nut == null) return 0;
        
        int doSauTrai = tinhDoSau(nut.trái);
        if (doSauTrai == -1) return -1;
        
        int doSauPhai = tinhDoSau(nut.phải);
        if (doSauPhai == -1) return -1;
        
        if (Math.abs(doSauTrai - doSauPhai) > 1) return -1;
        return Math.max(doSauTrai, doSauPhai) + 1;
    }
}

Đường Đi Trong Cây

class GiảiPháp {
    public List<String> duongDiCay(Đỉnh gốc) {
        List<String> kq = new ArrayList<>();
        if (gốc != null) timDuong(gốc, "", kq);
        return kq;
    }
    
    private void timDuong(Đỉnh nut, String duongDi, List<String> kq) {
        if (nut == null) return;
        
        StringBuilder sb = new StringBuilder(duongDi);
        if (sb.length() > 0) sb.append("->");
        sb.append(nut.val);
        
        if (nut.trái == null && nut.phải == null) {
            kq.add(sb.toString());
            return;
        }
        timDuong(nut.trái, sb.toString(), kq);
        timDuong(nut.phải, sb.toString(), kq);
    }
}

Tổng Lá Trái

class GiảiPháp {
    public int tongLaTrai(Đỉnh gốc) {
        if (gốc == null) return 0;
        int tong = 0;
        
        if (gốc.trái != null && gốc.trái.trái == null && gốc.trái.phải == null) {
            tong += gốc.trái.val;
        }
        tong += tongLaTrai(gốc.trái);
        tong += tongLaTrai(gốc.phải);
        return tong;
    }
}