02 算法体系班 - 11 二叉树算法题 - 《java笔记》

二叉树一些题目

二叉树一些题目

题目1：按层遍历二叉树

其实就是宽度优先遍历，用队列

public static void levelTravesalBT(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        System.out.print(node.value + " ");
    }
}

题目2：实现二叉树的序列化和反序列化

 /*
     * 通过先序遍历序列化
 * */
public static Queue<String> preSerialize(TreeNode root) {
    Queue<String> queue = new LinkedList<>();
    pres(root, queue);
    return queue;
}
private static void pres(TreeNode treeNode, Queue<String> queue) {
    if (treeNode == null) {
        queue.offer(null);
    } else {
        queue.add(String.valueOf(treeNode.value));
        pres(treeNode.left, queue);
        pres(treeNode.right, queue);
    }
}
public static TreeNode buildByPreSerialize(Queue<String> queue) {
    if (queue == null || queue.size() == 0) {
        return null;
    }
    return preBuild(queue);
}
private static TreeNode preBuild(Queue<String> queue) {
    String val = queue.poll();
    if (val == null) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(val));
    root.left = preBuild(queue);
    root.right = preBuild(queue);
    return root;
}
// for test
public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
}
// for test
public static TreeNode generate(int level, int maxLevel, int maxValue) {
    if (level > maxLevel || Math.random() < 0.5) {
        return null;
    }
    TreeNode root = new TreeNode((int) (Math.random() * maxValue));
    root.left = generate(level + 1, maxLevel, maxValue);
    root.right = generate(level + 1, maxLevel, maxValue);
    return root;
}
public static boolean isSameValueStructure(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 != null ^ root2 != null) {
        return false;
    }
    if (root1.value != root2.value) {
        return false;
    }
    return isSameValueStructure(root1.left, root2.left) && isSameValueStructure(root1.right, root2.right);
}
// for test
public static void printTree(TreeNode root) {
    System.out.println("Binary Tree:");
    printInOrder(root, 0, "H", 17);
    System.out.println();
}
public static void printInOrder(TreeNode root, int height, String to, int len) {
    if (root == null) {
        return;
    }
    printInOrder(root.right, height + 1, "v", len);
    String val = to + root.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(root.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();
}

/*
 * 通过后序遍历序列化
 * */

public static Queue<String> posSerialize(TreeNode root) {
    Queue<String> queue = new LinkedList<>();
    poss(root, queue);
    return queue;
}

private static void poss(TreeNode treeNode, Queue<String> queue) {
    if (treeNode == null) {
        queue.offer(null);
    } else {
        poss(treeNode.left, queue);
        poss(treeNode.right, queue);
        queue.offer(String.valueOf(treeNode.value));
    }
}

public static TreeNode buildByPosSerialize(Queue<String> queue) {
    if (queue == null || queue.size() == 0) {
        return null;
    }
    Stack<String> stack = new Stack<>();
    while (!queue.isEmpty()) {
        stack.push(queue.poll());
    }
    return posBuild(stack);
}

private static TreeNode posBuild(Stack<String> stack) {
    String val = stack.pop();
    if (val == null) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(val));
    root.right = posBuild(stack);
    root.left = posBuild(stack);
    return root;
}

/*
 * 通过按层遍历序列化
 * */

public static Queue<String> levelSerialize(TreeNode root) {
    Queue<String> queue = new LinkedList<>();

    Queue<TreeNode> help = new LinkedList<>();
    if (root == null) {
        queue.offer(null);
    } else {
        queue.offer(String.valueOf(root.value));
        help.offer(root);
        while (!help.isEmpty()) {
            TreeNode cur = help.poll();
            if (cur.left == null) {
                queue.offer(null);
            } else {
                queue.offer(String.valueOf(cur.left.value));
                help.offer(cur.left);
            }
            if (cur.right == null) {
                queue.offer(null);
            } else {
                queue.offer(String.valueOf(cur.right.value));
                help.offer(cur.right);
            }
        }
    }
    return queue;
}

public static TreeNode buildByLevelSerialize(Queue<String> queue) {
    if (queue == null || queue.size() == 0) {
        return null;
    }

    String val = queue.poll();
    TreeNode root = generateTreeNode(val);
    Queue<TreeNode> help = new LinkedList<>();
    if (root != null) {
        help.offer(root);
    }

    while (!help.isEmpty()) {
        TreeNode cur = help.poll();
        cur.left = generateTreeNode(queue.poll());
        cur.right = generateTreeNode(queue.poll());
        if (cur.left != null) {
            help.offer(cur.left);
        }
        if (cur.right != null) {
            help.offer(cur.right);
        }
    }
    return root;
}

private static TreeNode generateTreeNode(String s) {
    if (s == null) {
        return null;
    } else {
        return new TreeNode(Integer.parseInt(s));
    }
}

题目3：Encode N-ary Tree to Binary Tree

一个多叉树，编码转换为颗二叉树，解码二叉树转换为一颗多叉树。


public class Node {

    protected int val;
    protected List<Node> children;

    protected Node() {
    }

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

    public Node(int val, List<Node> children) {
        this.val = val;
        this.children = children;
    }
}

public class TreeNode {
    protected int val;
    protected TreeNode left;
    protected TreeNode right;

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


public TreeNode encode(Node root) {
    if (root == null) {
        return null;
    }
    TreeNode head = new TreeNode(root.val);
    head.left = encode(root.children);
    return head;
}

private TreeNode encode(List<Node> children) {
    TreeNode head = null;
    TreeNode cur = null;
    for (Node child : children) {
        TreeNode treeNode = new TreeNode(child.val);
        if (head == null) {
            head = treeNode;
        } else {
            cur.right = treeNode;
        }
        cur = treeNode;
        cur.left = encode(child.children);
    }
    return head;
}


public Node decode(TreeNode root) {
    if (root == null) {
        return null;
    }
    return new Node(root.val, de(root.left));
}

private List<Node> de(TreeNode root) {
    List<Node> children = new ArrayList<>();
    while (root != null) {
        Node cur = new Node(root.val, de(root.left));
        children.add(cur);
        root = root.right;
    }
    return children;
}

题目4：打印一颗二叉树

public static void printTree(TreeNode head) {
    System.out.println("Binary Tree:");
    printInOrder(head, 0, "H", 17);
    System.out.println();
}

private static void printInOrder(TreeNode head, int height, String to, int len) {
    if (head == null) {
        return;
    }
    printInOrder(head.right, height + 1, "v", len);

    String val = to + head.val + 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);
}

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

题目5：求二叉树最宽的层有多少个节点

public static int maxWidth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    TreeNode curLevelEndNode = root;
    TreeNode nextLevelEndNode = null;
    int curLevelNodeNum = 0;
    int max = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if (cur.left != null) {
            queue.offer(cur.left);
            nextLevelEndNode = cur.left;
        }
        if (cur.right != null) {
            queue.offer(cur.right);
            nextLevelEndNode = cur.right;
        }
        curLevelNodeNum++;
        if (cur == curLevelEndNode) {
            max = Math.max(max, curLevelNodeNum);
            curLevelEndNode = nextLevelEndNode;
            curLevelNodeNum = 0;
        }
    }
    return max;
}

public static int maxWidthUseMap(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    HashMap<TreeNode, Integer> levelMap = new HashMap<>(16);
    levelMap.put(root, 1);
    int curLevel = 1;
    int curLevelNodes = 0;
    int max = 0;
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        int curNodeLevel = levelMap.get(cur);
        if (cur.left != null) {
            queue.offer(cur.left);
            levelMap.put(cur.left, curNodeLevel + 1);
        }
        if (cur.right != null) {
            queue.offer(cur.right);
            levelMap.put(cur.right, curNodeLevel + 1);
        }
        if (curNodeLevel == curLevel) {
            curLevelNodes++;
        } else {
            max = Math.max(max, curLevelNodes);
            curLevel++;
            curLevelNodes = 1;
        }
    }
    max = Math.max(max, curLevelNodes);
    return max;
}

题目6 后继节点

题目：给你二叉树中的某个节点，返回该节点的后继节点。
后继节点：一棵二叉树，在中序遍历中，一个结点的下一个结点！


static class Node {
    int value;
    Node left;
    Node right;
    Node parent;

    public Node(int value) {
        this.value = value;
    }
}

// 给你二叉树中的某个节点，返回该节点的后继节点


public static Node getSuccessorNode(Node node) {
    if (node == null) {
        return null;
    }
    if (node.right != null) {
        return getLeftMost(node.right);
    } else {
        Node parent = node.parent;
        while (parent != null && parent.right == node) {
            node = parent;
            parent = node.parent;
        }
        return parent;
    }
}

private static Node getLeftMost(Node node) {
    if (node == null) {
        return null;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

题目7 折纸打印折痕

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up

类似二叉树中序遍历，折痕二叉树，每个左节点为凹，右节点为凸。二叉树层数为折的次数。

public static void printAllFolds(int n) {
    process(1, n, true);
}

private static void process(int i, int n, boolean down) {
    if (i > n) {
        return;
    }
    process(i + 1, n, true);
    System.out.print(down ? "凹 " : "凸 ");
    process(i + 1, n, false);
}