[数据结构与算法]leetcode 二叉树进阶题目

二叉树进阶题目

leetcode 510 二叉搜索树中的中序后继 II

思路：寻找二叉树中序后继的判定依据：1. 若当前结点有右子树，则其中序后继为右子树最左结点；2. 若当前结点没有右子树，则一路向上判定当前结点是否为父节点的右子树，若是右子树则继续向上检查，直到当前结点为起父节点的左子树时，返回父结点就是答案。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node == null) return null;
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node  = node.left;
            }
            return node;
        }else {
            while (node.parent != null && node == node.parent.right) {
                node = node.parent;
            }
            return node.parent;
        }
    }
}

leetcode 297 二叉树序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
思路： 这里使用二叉树的中序遍历序列化与反序列化，序列化与反序列化的过程比较简单，就是将正常结点用vlaue_表示，null结点使用#表示，反序列化时，使用“”符号将字符串分割为数组进行反序列化，树重建的过程使用了递归的方法，这一点是新学到的知识，还需要加以巩固。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        process(sb, root);
        return sb.toString();
    }

    public void process(StringBuilder sb, TreeNode root) {
        if (root == null) {
            sb.append("#_");
            return;
        }
        sb.append(root.val+"_");
        process(sb, root.left);
        process(sb, root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        TreeNode head = new TreeNode();
        String[] arr = data.split("_");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        return build(queue);
    }

    public TreeNode build(Queue<String> queue) {
        String value = queue.poll();
        if (value.equals("#")) return null;
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = build(queue);
        head.right = build(queue);
        return head;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

leetcode 449 序列化和反序列化二叉搜索树

和上面的题目基本一致

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        process(sb, root);
        return sb.toString();
    }

    public void process(StringBuilder sb, TreeNode root) {
        if (root == null) {
            sb.append("#_");
            return;
        }
        sb.append(root.val+"_");
        process(sb, root.left);
        process(sb, root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] arr = data.split("_");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        return build(queue);
    }

    public TreeNode build(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals("#")) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(val));
        head.left = build(queue);
        head.right = build(queue);
        return head;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

leetcode 331 验证二叉树的前序序列化

列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 “1,3” 。
注意：不允许重建树。
思路： 二叉树中每有一个结点就会有两个结点的空位，因此，使用栈，先将第一个节点的槽位压入栈中，每个新槽位的初始值都为2；每读到一个非空节就从栈顶弹出槽位，减1后判断是否不为0，不为0就将该槽位继续压入栈中，在压入一个新槽位；若读到一个空结点则从栈顶弹出槽位，减1后判断是否不为0，不为0就将该槽位继续压入栈中。

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder.equals(" ") || preorder.equals("#")) return true;
        String[] arr = preorder.split(",");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        Stack<Integer> stack = new Stack<>();
        if (!queue.poll().equals("#"))
            stack.push(2);
        while (!queue.isEmpty()) {
            String val = queue.poll();
            if (stack.isEmpty()) return false;
            if (val.equals("#")) {
                int top1 = stack.pop() - 1;
                if (top1 > 0) {
                    stack.push(top1);
                }
            }else {
                int top = stack.pop() - 1;
                if (top > 0) {
                    stack.push(top);
                }
                stack.push(2);
            }
        }

        return stack.isEmpty();
    }
}

leetcode 105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
**思路：**根据二叉树的前序与中序序列恢复一颗二叉树，整体上使用递归的方法完成二叉树的建立。前序为根左右，中序为左根右，因此可以从前序序列的第一个值必定为根节点，再从中序遍历序列中找到该根节点，之后可以将这颗数的左子树以及右子树前序序列和中序序列剥离出来，进而继续完成左右子树的建立。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return process(preorder, inorder);
    }

    public TreeNode process(int[] preorder, int[] inorder) {
        TreeNode head = null;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) { // 找到了根节点
                head = new TreeNode(inorder[i]); // 建立根节点
                if (i != 0) { // 只有i!=0，才有左子树
                    // 构造子树的preorder 和inorder数组
                    int[] leftSubInorder = new int[i];
                    int[] leftSubPreorder = new int[i];
                    for (int j = 0; j < i; j++) {
                        leftSubInorder[j] = inorder[j];
                        leftSubPreorder[j] = preorder[j+1];
                    }
                    head.left = process(leftSubPreorder, leftSubInorder);
                }
                if (i != inorder.length - 1) { // 只有i!=inorder.length-1, 才有右子树
                    // 构造右子树先序数组和中序数组
                    int[] rightSubInorder = new int[inorder.length-i-1];
                    int[] rightSubPreorder = new int[inorder.length-i-1];
                    for (int k = i+1; k < inorder.length; k++) {
                        rightSubInorder[k-i-1] = inorder[k];
                        rightSubPreorder[k-i-1] = preorder[k];
                    }
                    head.right = process(rightSubPreorder, rightSubInorder);
                }
            }
        }
        return head;
    }
}

leetcode 106. 从中序与后序遍历序列构造二叉树

与上题基本一致，只不过根节点要从后序序列最后面开始找。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return process(inorder, postorder);
    }

    public TreeNode process(int[] inorder, int[] postorder) {
        TreeNode head = null;
        int len = inorder.length;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == postorder[len-1]) {
                head = new TreeNode(inorder[i]);
                if (i != 0) { // 有左子树
                    // 构造左子树中序，后续序列数组
                    int[] leftSubInorder = new int[i];
                    int[] leftSubPostorder = new int[i];
                    for (int j = 0; j < i; j++) {
                        leftSubInorder[j] = inorder[j];
                        leftSubPostorder[j] = postorder[j];
                    }
                    head.left = process(leftSubInorder, leftSubPostorder);
                }
                if (i != len-1) { // 有右子树
                    int[] rightSubInorder = new int[len-i-1];
                    int[] rightSubPostorder = new int[len-i-1];
                    for (int k = i+1; k < len; k++) {
                        rightSubInorder[k-i-1] = inorder[k];
                        rightSubPostorder[k-i-1] = postorder[k-1];
                    }
                    head.right = process(rightSubInorder, rightSubPostorder);
                }
            }
        }
        return head;
    }
}