1. 

public class Node<V> {
    V value;
    Node<V> left;
    Node<V> right;
}

2.

2.1 

public static void traversal(Node root) {
    if (root == null) {
        return ;
    }
    System.out.println(root.value);
    traversal(root.left);
    System.out.println(root.value);
    traversal(root.right);
    System.out.println(root.value);
}

[ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

value 3 traversal 3

2.2

2.1 

public static void traversal(Node root) {
    // 
    if (root == null) {
        return ;
    }
    // 
    traversal(root.left);
    // 
    // 
    traversal(root.right);
    // 
    // 
}

Java

  • > traversal(root.left)

  • traversal(root.left) > traversal(root.right)

  • traversal(root.right) >

2.1 value 3 2.1 value 3

2.3

2.3.1

2.1 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

[ 1( ), 2( ), 4( ), 4, 4, 2, 5( ), 5, 5, 2, 1, 3( ), 6( ), 6, 6, 3, 7( ), 7, 7, 3, 1 ]

[1, 2, 4, 5, 3, 6, 7]

public static void preOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    System.out.println(root.value);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

2.3.2

2.1 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

[ 1, 2, 4, 4( ), 4, 2( ), 5, 5( ), 5, 2, 1( ), 3, 6, 6( ), 6, 3( ), 7, 7( ), 7, 3, 1 ]

[ 4, 2, 5, 1, 6, 3, 7 ]

public static void inOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    inOrderTraversal(root.left);
    System.out.println(root.value);
    inOrderTraversal(root.right);
}

2.3.3

2.1 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

[ 1, 2, 4, 4, 4( ), 2, 5, 5, 5( ), 2( ), 1, 3, 6, 6, 6( ), 3, 7, 7, 7( ), 3( ), 1( ) ]

[ 4, 5, 2, 6, 7, 3, 1 ]

public static void postOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.value);
}

2.4

2.4.1

    1. cur
    2. cur
    3. cur ( )

public static void preOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}

2.4.2

    1. ( )
    3. ( )

= + 

public static void inOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stack = new Stack<>();
    // , 
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            System.out.println(root.value);
            root = root.right;
        }
    }
}

2.4.3

  2. A
    1. cur A
    2. cur B
    3. cur A A ( )
  4. B 

public static void postOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stackA = new Stack<>();
    Stack<Node> stackB = new Stack<>();
    stackA.push(root);
    while (!stackA.isEmpty()) {
        Node cur = stackA.pop();
        stackB.push(cur);
        if (cur.left != null) {
            stackA.push(cur.left);
        }
        if (cur.right != null) {
            stackA.push(cur.right);
        }
    }
    while (!stackB.isEmpty()) {
        System.out.println(stackB.pop().value);
    }
}

2.5 

public static void depthFirstSearch(Node root) {
    preOrderTraversal(root);
}

2.6

    1. cur
    2. cur ( )
    3. cur ( )

  1. Java LinkedList
  2. FIFO 

public static void breadthFirstSearch(Node root) {
    if (root == null) {
        return ;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

3.

90

  • H1H 1
  • ^2^ 2
  • v3v 3 
// 
public static void printBinaryTree(Node head) {
    System.out.println("Binary Tree:");
    printInOrder(head, 0, "H", 17);
    System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len) {
    if (head == null) {
        return;
    }
    printInOrder(head.right, height + 1, "v", len);
    String val = to + head.value + to;
    int lenM = val.length();
    int lenL = (len - lenM)/2;
    int lenR = len - lenM - lenL;
    val = getSpace(lenL) + val + getSpace(lenR);
    System.out.println(getSpace(height * len) + val);
    printInOrder(head.left, height + 1, "^", len);
}

public static String getSpace(int num) {
    String space = " ";
    StringBuffer buf = new StringBuffer("");
    for (int i = 0; i < num; i++) {
        buf.append(space);
    }
    return buf.toString();
}

4.

4.1

4.2

  • value
  • _
  • #

value value "_" null value "#"

4.3

4.3.1 

public static String serialize(Node root) {
    if (root == null) {
        return "#_";
    }
    StringBuilder charSequence = new StringBuilder();
    charSequence.append(root.value + "_");
    charSequence.append(serialize(root.left));
    charSequence.append(serialize(root.right));
    return charSequence.toString();
}

4.3.1 

public static Node deserialize(String charSequence) {
    // 
    String[] values = charSequence.split("_");
    Queue<String> queue = new LinkedList<>();
    for (int i = 0; i < values.length; i ++) {
        queue.add(values[i]);
    }
    // 
    return process(queue);
}

public static Node process(Queue<String> queue) {
    String value = queue.poll();
    // null
    if ("#".equals(value)) {
        return null;
    }
    Node root = new Node(Integer.parseInt(value));
    root.left = process(queue);
    root.right = process(queue);
    return root;
}

5.

5.1

5.1.1

5.1.2

5.1.3 

// 
private static Node pre = null;

public static boolean isBST(Node root) {
    if (root == null) {
        return true;
    }
    boolean isLeftBST = isBST(root.left);
    if (!isLeftBST) {
        return false;
    }
    // 
    if (pre != null && pre.value >= root.value) {
        return false;
    } else {
        pre = root;
    }
    return isBST(root.right);
}
 

public static boolean isBST(Node root) {
    if (root == null) {
        return true;
    }
    Stack<Node> stack = new Stack<>();
    // 
    Node pre = null;
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            Node cur = stack.pop();
            // 
            if (pre != null && pre.value >= cur.value) {
                return false;
            } else {
                pre = cur;
            }
            root = cur.right;
        }
    }
    return true;
}

5.2

5.2.1

5.2.2

5.2.3 

public static boolean isCBT(Node root) {
    if (root == null) {
        return true;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    // , true
    boolean flag = false;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        // 
        if (cur.left == null && cur.right != null) {
            return false;
        }
        // , flag
        if (cur.left == null || cur.right == null) {
            flag = true;
        }
        // flag true , 
        if (flag && !(cur.left == null && cur.right == null)) {
            return false;
        }
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
    return true;
}

5.3

5.3.1

L N N = 2^L - 1

5.3.2

5.3.3

  3. N = 2^L - 1 

public static boolean isFBT(Node root) {
    if (root == null) {
        return true;
    }
    int depth = getDepth(root);
    int count = getCount(root);
    // 
    return count == (int) Math.pow(2, depth) - 1;
}

// 
public static int getDepth(Node root) {
    if (root == null) {
        return 0;
    }
    int leftD = getDepth(root.left);
    int rightD = getDepth(root.right);
    return Math.max(leftD, rightD) + 1;
}

// 
public static int getCount(Node root) {
    if (root == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int count = 1;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            count ++;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            count ++;
        }
    }
    return count;
}

5.4

5.4.1

1

5.4.2

5.4.3

  3. 1

6.3

6.3

6.

6.1

" "

DP

" " " " DP

DP

6.2 

// 
static class Info {
   ...
}

// , 
public static xxx xxx(Node root) {
    ...
}

// 
public static Info process(Node root) {
    //base case 
    if (root == null) {
        return xxx;
    }
    // 
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 
    ...
    // 
    return new Info(xxx)
}

6.3

5.4.3 " "

1

x x x

  1. x
  2. x
  3. x 1

[ ] 

// 
static class Info {
    boolean isBBT;
    int depth;
    R(boolean isBBT, int depth) {
        this.isBBT = isBBT;
        this.depth = depth;
    }
}

public static boolean isBBT(Node root) {
    return process(root).isBBT;
}

public static Info process(Node root) {
    if (root == null) {
        return new Info(true, 0);
    }
    // 
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 
    int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
    boolean isBBT = false;
    // 1
    if (leftInfo.isBBT && rightInfo.isBBT && Math.abs(leftInfo.depth - rightInfo.depth) <= 1) {
        isBBT = true;
    }
    // 
    return new Info(isBBT, depth);
}

6.

6.1

  • HashMap 

public static int getMaxBreadth(Node root) {
    if (root == null) {
        return -1;
    }
    // 
    int curLayer = 1;
    // 
    int curLayerNodesNum = 0;
    // 
    int broadestLayerNodesNum = Integer.MIN_VALUE;
    // , 
    HashMap<Node, Integer> map = new HashMap<>();
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    // 
    map.put(root, 1);
    
    // 
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        // 
        int curNodeLayer = map.get(cur);
        // 
        if (curNodeLayer == curLayer) {
            curLayerNodesNum ++;
        } else {
            // 
            broadestLayerNodesNum = Math.max(broadestLayerNodesNum, curLayerNodesNum);
            // 
            curLayer ++;
            // 
            curLayerNodesNum = 1;
        }
        if (cur.left != null) {
            queue.add(cur.left);
            // 
            map.put(cur.left, curNodeLayer + 1);
        }
        if (cur.right != null) {
            queue.add(cur.right);
            // 
            map.put(cur.right, curNodeLayer + 1);
        }
    }
 	// , , 
   	return Math.max(broadestLayerNodesNum, curLayerNodesNum);
}

6.2

[ ]

static class Info {
    // 
    int depth;
    // 
    int count;
    public Info(int depth, int count) {
        this.depth = depth;
        this.count = count;
    }
}

public static boolean isFBT(Node root) {
    Info info = process(root);
    int depth = info.depth;
    int count = info.count;
    //return count == (int) Math.pow(2, depth) - 1;
    return count == (1 << depth) - 1;
}

public static Info process(Node root) {
    if (root == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 
    int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
    // 
    int count = leftInfo.count + rightInfo.count + 1;
    return new Info(depth, count);
}

6.3

  1. x
  2. x
  3. x < x
  4. x > x

[ ]

// 
static class Info {
    // 
    boolean isSBT;
    // 
    int maxValue;
    // 
    int minValue;
    public R(boolean isSBT, int maxValue, int minValue) {
        this.isBST = isSBT;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
}

public static boolean isSBT(Node root) {
    return process(root).isSBT;
}

public static Info process(Node root) {
    if (root == null) {
        return null;
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    boolean isSBT = true;
    // 
    int maxValue = root.value;
    int minValue = root.value;
    // 
    if (leftInfo != null) {
        maxValue = Math.max(leftInfo.maxValue, maxValue);
        minValue = Math.min(leftInfo.minValue, minValue);
    }
    if (rightInfo != null) {
        maxValue = Math.max(rightInfo.maxValue, maxValue);
        minValue = Math.min(rightInfo.minValue, minValue);
    }
    // , BST 
    if (leftInfo != null && (!leftInfo.isSBT || leftInfo.maxValue >= root.value)) {
        isSBT = false;
    }
    // , BST 
    if (rightInfo != null && (!rightInfo.isSBT || rightInfo.minValue <= root.value)) {
        isSBT = false;
    }
    return new Info(isSBT, maxValue, minValue);
}

process base case new R(true, xxx, xxx) minValue maxValue null null

6.4

node1 node2

node1 node2

6.4.1

HashMap HashSet node1 node2 HashSet node2 HashSet 

public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
    if (root == null) {
        return null;
    }
    HashMap<Node, Node> map = new HashMap<>();
    // , 
    map.put(root, root);
    // 
    process(root, map);
    HashSet<Node> set = new HashSet<>();
    // 
    set.add(root);
    // node1 
    Node cur = node1;
    while (cur != map.get(cur)) {
        set.add(cur);
        cur = map.get(cur);
    }
    // node2 
    cur = node2;
    while (true) {
        // 
        if (set.contains(cur)) {
            return cur;
        }
        set.add(cur);
        cur = map.get(cur);
    }
}

public static void process(Node root, HashMap<Node, Node> map) {
    if (root == null) {
        return ;
    }
    process(root.left, map);
    process(root.right, map);
    // 
    if (root.left != null) {
        map.put(root.left, root);
    }
    if (root.right != null) {
        map.put(root.right, root);
    }
}

6.4.2

  1. node1 node2
  2. node2 node1
  3. node1 node2

  1. 1 2
  2. 3 

public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
    if (root == null || root == node1 || root == node2) {
        return root;
    }
    Node left = lowestCommonAncestor(root.left, node1, node2);
    Node right = lowestCommonAncestor(root.right, node1, node2);
    if (left != null && right != null) {
        return root;
    }
    return left != null ? left : right;
}

node1 node2 null

node1 node2

node1 node2

6.5

:

public class Node {
    int value;
    Node left;
    Node right;
    Node parent;
}

parent

Node parent parent null node node

O(N)

  • node node

  • node node

O(N)

1

D B 1 D parent B E A 2 E parent A

Y X K O(K)

parent

  • X X

  • X X X X

  • X null 

public static Node findSuccessorNode(Node root, Node target) {
    if (root == null) {
        return null;
    }
    Node cur = target.right;
    // 
    if (cur != null) {
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }
    // 
    else {
        cur = target;
        while (cur.parent != null) {
            if (cur == cur.parent.left) {
                return cur.parent;
            }
            cur = cur.parent;
        }
        // , null
        return null;
    }
}

6.6

1

2 3

N N

N = 1 down

N = 2 down down up

  • 1

  • 2 

public static void paperFolding(int N) {
    // down
    process(N, 1, true);
}

/**
     * @param N      
     * @param depth  
     * @param direction  ,true down,false up
     */
public static void process(int N, int depth, boolean direction) {
    if (depth > N) {
        return ;
    }
    // down
    process(N, depth + 1, true);
    System.out.print(direction ? "down " : "up ");
    // up
    process(N, depth + 1, false);
}