7.12号刷题

第一题 450. Delete Node in a BST

题目描述

给定一个BST的根节点与一个key，删除BST中key对应的节点。返回BST根节点的引用（有可能被更新）。

基本上，删除操作分为两个阶段：

寻找待删除节点。
如果节点找到，删掉这个节点。
注意：时间复杂度为O(树的高度)。

算法

利用双回溯，首先找到需要删除的节点。然后找到下一个最小值，替换当前值。然后再删除那个最小值。

有三种情况

1. 如果左边为空，那么直接替换为右边
2. 如果右边为空，直接替换为左边
3. 如果不会空，按照上述描述进行节点删除

public class deleteNode450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            TreeNode nextMin = root.right;
            while (nextMin.left != null) nextMin = nextMin.left;
            root.val = nextMin.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
}

第二题 114. Flatten Binary Tree to Linked List

题目描述

将一棵树，按照前序遍历的顺序，拍平。

算法

Iterative

public class flatten114 {
    public void flatten2(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        TreeNode pre = null;
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);

            if (pre != null) {
                pre.left = null;
                pre.right = cur;
            }
            pre = cur;
        }
    }
}

Recursive

public class Solution {
    TreeNode pre = null;
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        flatten(root.right);
        flatten(root.left);
        
        root.right = pre;
        root.left = null;
        pre = root;   
    }
}

第三题 297. Serialize and Deserialize Binary Tree

题目描述

序列化是将数据结构或者对象转换成比特序列的过程，以便将其存入文件或者内存缓冲区，或者通过网络连接进行传输，以后在本机或者其他电脑环境重建。

设计一个算法序列化、反序列化一棵二叉树。对于算法的序列化/反序列化的实现方式没有限制。你只需要能够确保二叉树可以序列化成一个字符串，并且可以反序列化成原始树结构即可。

例如，你可以将题目描述中的例子序列化为：”[1,2,3,null,null,4,5]”，与LeetCode OJ序列化一棵二叉树的方式相同。你不一定非要遵从这种格式，请勇于创新，并想出不同的方法来。

注意：不要使用类成员/全局/静态变量来存储状态。你的序列化与反序列化算法应当是无状态的。

算法

Recursive

public class Codec297 {

    private static final String SPLIT = ",";
    private static final String NULL = "null";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        return sb.toString();
    }

    public void helper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SPLIT);
        } else {
            sb.append(root.val).append(SPLIT);
            helper(root.left, sb);
            helper(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(SPLIT)));
        return recover(nodes);
    }

    public TreeNode recover(Queue<String> queue) {
        String cur = queue.poll();
        if (cur.equals(NULL)) return null;
        else {
            TreeNode root = new TreeNode(Integer.valueOf(cur));
            root.left = recover(queue);
            root.right = recover(queue);
            return root;
        }
    }
}

Iterative

将每一层的数字推入queue中，queue的左右必定是其后面两位。

之后利用queue进行还原

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                sb.append("null").append(",");
                continue;
            }
            sb.append(cur.val).append(",");
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return sb.toString();        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") return null;
        Queue<TreeNode> queue = new LinkedList<>();
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = queue.poll();
            if (!values[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                queue.add(left);
            }
            if (!values[++i].equals("null")) {
                TreeNode right  = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                queue.add(right);
            }
        }
        return root;        
    }
}

第四题 222. Count Complete Tree Nodes

题目描述

计算整个树中有多少个Node节点

算法

首先计算left的深度，再计算right的深度。如果深度相同，对于这课树（子树）而言，节点树为2^n - 1。通过不断回溯，减小范围

public class countNodes222 {
    public int countNodes(TreeNode root) {
        int leftDepth = countLeft(root);
        int rightDepth = countRight(root);
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        } else {
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }

    public int countRight(TreeNode root) {
        int depth = 0;
        while (root != null) {
            root = root.right;
            depth++;
        }
        return depth;
    }

    public int countLeft(TreeNode root) {
        int depth = 0;
        while (root != null) {
            root = root.left;
            depth++;
        }
        return depth;
    }
}

第五题 124. Binary Tree Maximum Path Sum

题目描述

给定一棵二叉树，寻找最大路径和。

对于本题，路径指的是从任意起始节点出发沿着父亲-孩子链接到达某个终止节点的节点序列。路径不一定要穿过根节点。

算法

对每一个节点当前值进行计算，并返回最大值

public class Solution {
    int maxValue;
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    
    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

第六题 99. Recover Binary Search Tree

题目描述

在一课二叉搜索树中，有两个值的位置发生了互换，求在不改变这棵树结构的情况下，恢复这棵树

算法

利用中序遍历，记录下值改变的点

public class Solution {
    TreeNode prev = new TreeNode(Integer.MIN_VALUE), first = null, second = null;
    public void recoverTree(TreeNode root) {
        traverse(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    
    public void traverse(TreeNode root) {
        if (root == null) return;
        
        traverse(root.left);
        if (first == null && prev.val > root.val) {
            first = prev;
        }
        
        if (first != null && prev.val > root.val) {
            second = root;
        }
        prev = root;
        traverse(root.right);
    }
}

第七题 333. Largest BST Subtree

题目描述

在一课二叉树中找到节点个数最多的BST

算法

满足BST，则：

1. root.val > 左边子树最大值
2. root.val < 右边子树最小值

因此，我们用int[3]记录下当前节点的情况。（1）是否是BST（2）最小值（3）最大值。并根据这个找到左右子树，对这棵树进行推断

public class largestBSTSubtree333 {
    int maxNumber = 0;
    public int largestBSTSubtree(TreeNode root) {
        helper(root);
        return maxNumber;
    }

    public int[] helper(TreeNode root) {
        //res[0] tag, res[1] left, res[2] right
        int[] res = new int[3];
        if (root == null) return res;

        int[] left = helper(root.left);
        int[] right = helper(root.right);

        if (((left[0] == 0) || (left[0] > 0 && root.val > left[2]))
                && ((right[0] == 0) || (right[0] > 0 && root.val < right[1]))) {
            int size = 1 + left[0] + right[0];
            int leftBoundary = left[0] == 0 ? root.val : left[1];
            int rightBoundary = right[0] == 0 ? root.val : right[2];
            res[0] = size;
            res[1] = leftBoundary;
            res[2] = rightBoundary;
        } else {
            res[0] = -1;
        }
        maxNumber = Math.max(maxNumber, res[0]);
        return res;
    }
}

第八题 545. Boundary of Binary Tree

题目描述

给定二叉树，逆时针输出二叉树的边界。边界包括左边界、叶子节点和右边界。

左边界是指从根出发到最左侧节点经过的路径。右边界是指从根出发到最右侧节点经过的路径。

如果根节点不包含左子树或者右子树，则对应的边界不存在。注意此定义是指整棵二叉树，不包含子树。

最左侧节点是指从根节点出发尽量向左走，如果不能则向右走，到达的叶子结点。

最右侧节点定义参考最左侧节点，左右互换即可。

算法

找到左侧骨架，右侧骨架，和所有的叶节点

public class boundaryOfBinaryTree545 {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        res.add(root.val);
        boundaries(root.left, true, res);
        leaves(root.left, res);
        leaves(root.right, res);
        boundaries(root.right, false, res);
        return res;
    }

    //tag = true, leftBoundary
    public void boundaries(TreeNode root, boolean tag, List<Integer> res) {
        if (root == null || (root.left == null) && (root.right == null)) return;

        if(tag) {
            res.add(root.val);
            if (root.left != null) boundaries(root.left, tag, res);
            else boundaries(root.right, tag, res);
        } else {
            if (root.right != null) boundaries(root.right, tag, res);
            else boundaries(root.left, tag, res);
            res.add(root.val);
        }
    }

    public void leaves(TreeNode root, List<Integer> res) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            res.add(root.val);
            return;
        }
        leaves(root.left, res);
        leaves(root.right, res);
    }
}

第九题 496. Next Greater Element I

题目描述

给定两个数组（无重复）nums1 与 nums2，其中nums1的元素是nums2的子集。在nums2中寻找大于nums1中对应位置且距离最近的元素。如果对应位置不存在这样的元素，则输出-1。

算法

利用stack存储下降的序列，如果遇到上升的序列，那么stack中小于这个数的所有数字，下一个最大数即为此数。

public class nextGreaterElement496 {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                map.put(stack.pop(), nums[i]);
            }
            stack.push(nums[i]);
        }

        for (int i = 0; i < findNums.length; i++) {
            findNums[i] = map.getOrDefault(findNums[i], -1);
        }
        return findNums;
    }
}