LeetCode(17) -- 538, 541,

P538. Convert BST to Greater Tree (Easy)

BST, 把每个点都替换为原来那个节点的数值加上所有比它大的数值的和。

我的思路

BST比大小当然还是中序遍历。不过这道题需要所有比它大的值，也就是说我需要从右向左遍历。

我的代码

public class E_538_ConvertBSTtoGreaterTree {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.right);
        node.val += sum;
        sum = node.val;
        dfs(node.left);
    }
}

99%

最优解

class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

P541. Reverse String II (Easy)

一个String 和一个整数k，只要有2k个字符，就反转前k个字符。如果剩下少于k个字符，都反转； 如果剩下大于等于k个字符，小于2k个字符，就只反转前k个字符。

我的思路

先用字符串的长度除以k，看有几个k,几个2k。然后做出相应的调换即可。

我的代码

public class E_514_ReverseStringII {
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (len <= 1) return s;
        char temp;
        int remainLength = len % (2*k);
        int numberOf2k = len / (2*k);
        if (numberOf2k >= 1) {
            for (int j = 0; j < numberOf2k; j++) {
                for (int i = j * 2 * k; i < j * 2 * k + k / 2; i++) {
                    temp = chars[i];
                    int r = j * 2 * k + k - i + j * 2 * k - 1;
                    chars[i] = chars[r];
                    chars[r] = temp;
                }
            }
        }
        if (remainLength == 0) {
            return new String(chars);
        } else if (remainLength < k) {
            for (int i = 0; i < remainLength / 2; i++) {
                temp = chars[len - remainLength + i];
                chars[len - remainLength + i] = chars[len - i - 1];
                chars[len - i - 1] = temp;
            }
        } else {
            for (int i = 0; i < k / 2; i++) {
                temp = chars[len - remainLength + i];
                int r = len - remainLength + k - 1 - i;
                chars[len - remainLength + i] = chars[r];
                chars[r] = temp;
            }
        }
        return new String(chars);
    }

}

69%

最优解

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        for (int start = 0; start < a.length; start += 2 * k) {
            int i = start, j = Math.min(start + k - 1, a.length - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

P543. Diameter of Binary Tree (Easy)

一个二叉树，求任意两点的最长的路径。

我的思路

我觉得最长路径应该是最大的深度加上第二大的深度。不对，未必。如果两个最深的叶都在一起，那它们的路径很短。

答案

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        ans = Math.max(ans, L+R+1);
        return Math.max(L, R) + 1;
    }
}

最优解

class Solution {
    int toReturn = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return toReturn;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        toReturn = Math.max(toReturn, left+right);
        return Math.max(left, right) +1;
    }
}

感觉这个代码读起来舒服得多。