LC655+offer070+offer069+offer072+662

输出二叉树

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

• 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
• 矩阵的列数 n 应该等于 $2^{height+1}$ - 1 。
• 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
• 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-$2^{height-r-1}$] ，右子节点放置在 res[r+1][c+$2^{height-r-1}$] 。
• 继续这一过程，直到树中的所有节点都妥善放置。
• 任意空单元格都应该包含空字符串 “” 。

返回构造得到的矩阵 res 。

分析:

首先要确定树的高度h, 根据树的高度初始化一个$(h+1)\times 2^{height+1}$ - 1$的矩阵, 先把每个位置的初始值都设为"",然后利用dfs对树从根节点开始遍历,若左子树不为空则在对应位置上填入其值,同样右子树也是.

class Solution {
    int h , m, n;
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> printTree(TreeNode root) {
        if (root==null) return null;
        getHeight(root, 0);
        m = h+1;
        n= (int) (Math.pow(2, h+1))-1;
        for (int i = 0; i < m; i++) {
            List<String> list = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                list.add("");
            }
            ans.add(list);

        }
        dfs(root, 0, (n-1)/2);
        return ans;



    }
    public void getHeight(TreeNode root, int depth){
        if (root == null) return;
        h = Math.max(depth, h);
        getHeight(root.left, depth+1);
        getHeight(root.right, depth+1);

    }
    public void dfs(TreeNode root, int r, int c){
        if (root==null) return;
        ans.get(r).set(c, String.valueOf(root.val));
        int t = (int) Math.pow(2, h-r-1);
        dfs(root.left, r+1, c-t);
        dfs(root.right, r+1, c+t);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

分析:

因为要求 O(log n) 时间复杂度和 O(1) 空间复杂度故想到使用二分查找.可以根据二分点mid的奇偶性进行分情况讨论:

• mid 为偶数下标：正常情况下偶数下标的值会与下一值相同，因此如果满足该条件，可以确保 mid 之前并没有插入单一元素。正常情况下，此时应该更新 l = mid，否则应当让 r = mid - 1，但需要注意这样的更新逻辑，会因为更新 r 时否决 mid 而错过答案，我们可以将否决 mid 的动作放到更新 l 的一侧，即需要将更新逻辑修改为 l = mid + 1 和 r = mid ；
• mid 为奇数下标：同理，根据上述结论，正常情况下奇数下标的值会与上一值相同，因此如果满足该条件，可以确保 mid 之前并没有插入单一元素，相应的更新 l 和 r。

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int res = 0;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (mid<n-1 && nums[mid] == nums[mid+1]){
                if (mid%2==0) l=mid+2;
                else r=mid-1;
            }
            else if (mid>0 && nums[mid] == nums[mid-1]){
                if (mid%2==0)  r=mid-2;
                else l=mid+1;
            }
            else {
                res = nums[mid];
                break;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

山峰数组的顶部

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

• arr.length >= 3
• 存在 i（0 < i < arr.length - 1）使得：
  • arr[0] < arr[1] < … arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > … > arr[arr.length - 1]

给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

分析:

由于需要复杂度O(log(n)) 的解决方案,故采用二分查找.利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。因此 以峰顶元素为分割点的 arr 数组，根据与 前一元素/后一元素 的大小关系，具有二段性：

• 峰顶元素左侧满足 arr[i-1] < arr[i] 性质，右侧不满足;
• 峰顶元素右侧满足 arr[i] > arr[i+1] 性质，左侧不满足;

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int l = 0, r = arr.length-1;
        int ans = 0;
        while (l<=r){
            int mid = (l+r)/2;
            if (arr[mid]>arr[mid+1]){
                ans = mid;
                r = mid-1;
            }else l = mid+1;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

求平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

分析:

使用二分查找,如果当前mid*mid<=x,则l=mid+1; 反之r=mid-1.

class Solution {
    public int mySqrt(int x) {
        if (x==0) return 0;
        int l = 0, r = x, ans=-1;
        while (l <= r){
            int mid = l + (r-l)/2;
            if ((long) mid*mid <= x){
                ans = mid;
                l = mid+1;
            }else r = mid - 1;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二叉树最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

分析:

使用DFS遍历二叉树, 同时用一个哈希表来记录当前遍历节点的. 根据满二叉树的节点编号规则：若根节点编号为 u，则其左子节点编号为 u << 1，其右节点编号为 u << 1 | 1。
在 DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度，最终所有层数中的最大宽度即是答案。而实现上利用先 DFS 左节点，再 DFS 右节点的性质可知，每层的最左节点必然是最先被遍历到，因此我们只需要记录当前层最先被遍历到点编号（即当前层最小节点编号），并在 DFS 过程中计算宽度，更新答案即可。

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 1, 0);
        return ans;
    }
    void dfs(TreeNode root, int u, int depth) {
        if (root == null) return ;
        if (!map.containsKey(depth)) map.put(depth, u);
        ans = Math.max(ans, u - map.get(depth) + 1);
        dfs(root.left, u << 1, depth + 1);
        dfs(root.right, u << 1 | 1, depth + 1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16