【Java】常用二叉木のポイント

今日は二叉樹の試験点を復習しました.反転二叉樹、二叉樹の最近の公共祖先を含めて、指定値の経路を見つけました.

import java.util.*;

public class buildTree {

    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    private static List nodeList = null;

    private static class Node {
        Node leftChild;
        Node rightChild;
        int data;

        Node(int newData) {
            leftChild = null;
            rightChild = null;
            data = newData;
        }
    }

    public static void main(String[] args) {
        buildTree binTree = new buildTree();
        binTree.createBinTree();
        // nodeList  0           
        Node root = nodeList.get(0);
        Node node1 = nodeList.get(7);
        Node node2 = nodeList.get(8);

        System.out.println("    ：");
        preOrderTraverse(root);
        System.out.println();

        System.out.println("    ：");
        inOrderTraverse(root);
        System.out.println();

        System.out.println("    ：");
        postOrderTraverse(root);
        System.out.println();

        int height = getHeight(root);
        System.out.println("tree height: " + height);

        int maxWidth = getMaxWidth(root);
        System.out.println("tree max width: " + maxWidth);
        System.out.println();

        int sum = 16;
        findPath(root, sum);

        Node leastCommonAncestor = findLeastCommonAncestor(root, node1, node2);
        System.out.println(leastCommonAncestor.data);

        reverseTree(root);
    }

    private static void reverseTree(Node root) {
        if (root == null) {
            return;
        }
        if ((root.leftChild == null) && (root.rightChild == null)) {
            return;
        }
        Node tmp = root.leftChild;
        root.leftChild = root.rightChild;
        root.rightChild = tmp;
        reverseTree(root.leftChild);
        reverseTree(root.rightChild);
    }
    

    private static Node findLeastCommonAncestor(Node root, Node node1, Node node2) {
        if (root == null) {
            return null;
        }
        if (root == node1 || root == node2) {
            return root;
        }
        Node left = findLeastCommonAncestor(root.leftChild, node1, node2);
        Node right = findLeastCommonAncestor(root.rightChild, node1, node2);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }




    private static void findPath(Node root, int sum) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack();
        findPath(root, sum, stack, 0);
    }

    private static void findPath(Node root, int sum, Stack stack, int curSum) {
        stack.push(root.data);
        curSum += root.data;

        boolean isLeaf = (root.leftChild == null) && (root.rightChild == null);
        if (isLeaf && curSum == sum) {
            for (Integer e : stack) {
                System.out.println(e);
            }
            System.out.println();
        }

        if (root.leftChild != null) {
            findPath(root.leftChild, sum, stack, curSum);
        }
        if (root.rightChild != null) {
            findPath(root.rightChild, sum, stack, curSum);
        }
        //      
        stack.pop();
    }



    public void createBinTree() {
        nodeList = new LinkedList();
        //             Node  
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
            nodeList.add(new Node(array[nodeIndex]));
        }
        //   lastParentIndex-1                        
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
            //    
            nodeList.get(parentIndex).leftChild = nodeList
                    .get(parentIndex * 2 + 1);
            //    
            nodeList.get(parentIndex).rightChild = nodeList
                    .get(parentIndex * 2 + 2);
        }
        //        :                ，         
        int lastParentIndex = array.length / 2 - 1;
        //    
        nodeList.get(lastParentIndex).leftChild = nodeList
                .get(lastParentIndex * 2 + 1);
        //    ,                
        if (array.length % 2 == 1) {
            nodeList.get(lastParentIndex).rightChild = nodeList
                    .get(lastParentIndex * 2 + 2);
        }
    }

    /**
     *     
     *
     *                ，           
     *
     * @param root
     *                 
     */
    public static void preOrderTraverse(Node root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        preOrderTraverse(root.leftChild);
        preOrderTraverse(root.rightChild);
    }

    /**
     *     
     *
     *                ，           
     *
     * @param root
     *                 
     */
    public static void inOrderTraverse(Node root) {
        if (root == null)
            return;
        inOrderTraverse(root.leftChild);
        System.out.print(root.data + " ");
        inOrderTraverse(root.rightChild);
    }

    /**
     *     
     *
     *                ，           
     *
     * @param root
     *                 
     */
    public static void postOrderTraverse(Node root) {
        if (root == null)
            return;
        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.print(root.data + " ");
    }



    public static int getHeight(Node root) {
        if (root == null) {
            return 0;
        } else {
            int left = getHeight(root.leftChild);
            int right = getHeight(root.rightChild);
            return (left > right ? left : right) + 1;
        }
    }

    public static int getMaxWidth(Node root) {
        Queue queue = new ArrayDeque();
        int maxWidth = 1;
        queue.add(root);

        while (true) {
            int len = queue.size();
            if (len == 0) {
                break;
            }
            while (len > 0) {
                Node t = queue.poll();
                len--;
                if (t.leftChild != null) {
                    queue.add(t.leftChild);
                }
                if (t.rightChild != null) {
                    queue.add(t.rightChild);
                }
            }
            maxWidth = Math.max(maxWidth, queue.size());
        }
        return maxWidth;
    }





}