나무의 범람, 두 갈래 나무 재건

class BinaryTreeNode {
    int val;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int val) {
        this.val = val;
    }
}

노드 작업 액세스

void visit(BinaryTreeNode node) {
    System.out.print(node.val + " ");
}

두 갈래 나무 노드 수

int TreeNodeCount(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    }
    return TreeNodeCount(root.left) + TreeNodeCount(root.right) + 1;
}

두 갈래 나무의 깊이를 구하다

int TreeDepth(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);
    return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
}

앞차례 를 두루 다니다

void preOrderTraverse(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    visit(root);                    // 
    preOrderTraverse(root.left);    // 
    preOrderTraverse(root.right);   // 
}

중서 역행

void inOrderTraverse(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    inOrderTraverse(root.left);     // 
    visit(root);                    // 
    inOrderTraverse(root.right);    // 
}

뒤돌아 다니다

void postOrderTraverse(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    postOrderTraverse(root.left);    // 
    postOrderTraverse(root.right);   // 
    visit(root);                    // 
}

레이어 반복 (위에서 아래로, 왼쪽에서 오른쪽)

void levelTraverse(BinaryTreeNode root){
    if (root == null) {
        return;
    }
    Queue queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BinaryTreeNode node = queue.poll();
        visit(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

두 갈래 나무를 재건하다

BinaryTreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if (pre == null || in == null || pre.length <= 0 || in.length <= 0) {
        return null;
    }
    // 
    BinaryTreeNode root = new BinaryTreeNode(pre[0]);
    int rootPositionInOrder = -1;
    // 
    for (int i = 0; i < in.length; i++) {
        if (root.val == in[i]) {
            rootPositionInOrder = i;
            break;
        }
    }
    if (rootPositionInOrder == -1) {
        return null;
    }
    // 
    int numOfLeft = rootPositionInOrder;
    // 
    int[] leftPre = new int[numOfLeft];
    for (int i = 0; i < numOfLeft; i++) {
        leftPre[i] = pre[i + 1];
    }
    // 
    int[] leftIn = new int[numOfLeft];
    for (int i = 0; i < numOfLeft; i++) {
        leftIn[i] = in[i];
    }
    // 
    root.left = reConstructBinaryTree(leftPre, leftIn);

    // 
    int numOfRight = in.length - numOfLeft - 1;
    // 
    int[] rightPre = new int[numOfRight];
    for (int i = 0; i < numOfRight; i++) {
        rightPre[i] = pre[i + numOfLeft + 1];
    }
    // 
    int[] rightIn = new int[numOfRight];
    for (int i = 0; i < numOfRight; i++) {
        rightIn[i] = in[i + numOfLeft + 1];
    }
    // 
    root.right = reConstructBinaryTree(rightPre, rightIn);

    return root;
}