数据结构与算法学习（十四）

1、返回二叉树的最大宽度

1.1、题目描述

给定一棵二叉树，返回这棵二叉树中结点数最多的那层的结点数量

• 示例一

    3
   / \
  9  20
 /  /  \
4  15   7

返回 3

• 示例二

    3
   / \
  9  20
 / \ / \
4  1 5  7
/       \
3        2

返回 4

1.2、解题思路

我们使用队列 + 符号位的方式来解决这道题，定义几个变量如下

• TreeNode curEnd：这个变量表示当前这一层的最后一个结点，初始化为 root，因为 root 为第一层的最后一个结点
• TreeNode nextEnd：这个变量表示当前层的下一层的最后一个结点，初始化为 null （不知道第二层有多少个结点）
• int max ：全局最大宽度
• int curLevelNodes：当前层的最大宽度

解题大致思路如下，这里以上面示例二给的二叉树为例

• 创建一个队列，然后让 root 结点入列

此时队列中存在结点 3 ，让结点 3 出列，如果当前出列的结点的左子树不为空，那么将 nextEnd 指向该结点的左子树，如果当前出列的结点的右子树不为空，那么将 nextEnd 指向该结点的右子树，这一步的目的是找到下一层的最右结点

以上面的二叉树为例，当我们 pop 出第一个结点 3 时，此时 nextEnd 被初始化为 null，此时由于 3 的左子树不为空，所以将 nextEnd 置为 3 的左子树 ，又因为它的右子树不为空，所以又将 nextEnd 置为 3 的右子树。

• 当队列中出栈的 cur 结点 == 当前层的最后一个结点 curEnd 时，代表这一层已经遍历完毕，此时我们将当前层的结点个数与全局最大宽度进行对比，然后更新 max （如果 curLevelNodes > max 的话）

由于当前队列出栈的 cur 结点为 3 ，即第一层的最后一个结点，所以此时我们需要更新 max ，将 max 更新为 1

• 在一层遍历完成后，我们需要进入下一层，此时将 curLevelNodes 的值重新置为 0 ，然后将当前 curEnd 置为 nextEnd （上一层的最后一个结点）

在第一层访问完后，我们需要对第二层进行访问，此时将 curLevelNodes 置为 0 ，同时将 curEnd 设置为 nextEnd （即第二层的最右结点 20 ）

1.3、解题代码

public static int maxWidth (TreeNode root) {
    if (root == null) return 0;
    // 变量一，当前层的最右结点，这个变量初始化为 root
    TreeNode curEnd = root;
    // 变量二，下一层的最右结点，这个变量初始化为 null
    TreeNode nextEnd = null;
    // 变量三，全局最大宽度，初始化为 0
    int maxWidth = 0;
    // 变量四，当前层的最大宽度，初始化为 0
    int currentLevelNodes = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    // 将 root 元素加入到队列中
    queue.add(root);
    // 将 root 结点加入到队列中
    while (!queue.isEmpty()) {
        // 此时弹出队列中的元素
        TreeNode currentNode = queue.poll();
        // 如果当前弹出队列中的元素的左子节点不为空，那么更新 nextEnd
        if (currentNode.left != null) {
            // 同时需要将它的左子节点加入到队列中
            queue.add(currentNode.left);
            nextEnd = currentNode.left;
        }
        // 同理，如果当前弹出队列中的元素的右子节点不为空，那么更新 nextEnd
        if (currentNode.right != null) {
            queue.add(currentNode.right);
            nextEnd = currentNode.right;
        }
        // 每次从栈中弹出数据时，都需要将当前层的结点数++
        currentLevelNodes++;
        // 如果当前队列弹出的元素是该层的最后一个元素，那么证明当前层的结点全部访问过
        // 此时我们需要进行结算
        if (currentNode == curEnd) {
            maxWidth = Math.max(maxWidth, currentLevelNodes);
            // 进入下一层前，需要将 currentLevelNodes 置为 0，同时将下一层的最右结点指定一下
            currentLevelNodes = 0;
            curEnd = nextEnd;
        }
    }
    return maxWidth;
}

2、二叉树的层序遍历

2.1、题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

• 示例

二叉树：[3,9,20,null,null,15,7]

  3
 / \
9  20
  /  \
 15   7

返回：

[
  [3],
  [9,20],
  [15,7]
]

• 方法声明

public List<List<Integer>> levelOrder(TreeNode root);

2.2、解题思路

这道题与上一题的解题思路大体相同，都是使用一个 curEnd 和 nextEnd 来判断每一层是否结束。

2.3、解题代码

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    TreeNode curEnd = root;
    TreeNode nextEnd = null;
    // 初始化一个列表，这个列表用于存放每一层的结点 value
    List<Integer> currentValues = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode currentNode = queue.poll();
        currentValues.add(currentNode.val);
        if (currentNode.left != null) {
            queue.add(currentNode.left);
            nextEnd = currentNode.left;
        }
        if (currentNode.right != null) {
            queue.add(currentNode.right);
            nextEnd = currentNode.right;
        }
        if (curEnd == currentNode) {
            // 证明该层已经访问结束
            result.add(currentValues);
            curEnd = nextEnd;
            // 在访问结束进入下一轮时，我们需要将这个列表数据清空
            currentValues = new ArrayList<>();
        }
    }
    return result;
}

3、二叉树的序列化和反序列化

3.1、概念说明

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

我们可以使用前序遍历，然后将二叉树的遍历结果保存在数组中，从而实现序列化，后面我们可以使用这个数组还原出二叉树的形状

在进行序列化时，我们需要使用 null 结点将一棵不满的二叉树补全为一棵 满二叉树，这是因为如果我们单纯只序列化不为空的结点，那么不能保证一个结果数组与一棵二叉树一一对应，比如说

• 以下两棵二叉树的前序遍历结果都是一样的

1                           1
  /                           /  \
 1				和            1     1
  \
   1         

但如果我们使用 null 结点将上面的二叉树补满，那么得到的就是遍历结果就是不一样的。

• 方法描述：序列化

public String serialize(TreeNode root);

• 方法描述：反序列化

public TreeNode deserialize(String data);

3.2、题目描述

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

3.3、解题思路

• 序列化

我们使用一个 StringBuilder 来拼接字符串，使用前序遍历进行序列化，这个字符串以符号 “[“ 开头

1. 当传入的结点为 null 时，此时我们需要拼接一个字符串 “null” ，然后拼接一个 “,” 符号作为我们反序列化的分隔符
2. 当传入的结点不为 null 时，将该结点的值拼接上去，同时拼接一个 “,” ，然后分别向左向右递归
3. 最后要返回字符串时，需要去除字符串中最后一个 “,” ，然后拼接上一个结束符 “]”

public String serialize(TreeNode root) {
    StringBuilder builder = new StringBuilder();
    builder.append("[");
    serialize(root, builder);
    String result = builder.toString();
    if (result.endsWith(",")) {
        result = result.substring(0, result.length() - 1);
    }
    result += "]";
    return result;
}

private void serialize(TreeNode root, StringBuilder builder) {
    if (root == null) {
        builder.append("null");
        builder.append(",");
    } else {
        builder.append(root.val);
        builder.append(",");
        serialize(root.left, builder);
        serialize(root.right, builder);
    }
}

• 反序列化

1. 我们需要去除字符串左右两边的 “[“ 和 “]”，然后根据分隔符 “,” 分割成数组，并将数组加入到队列中
2. 对于前序遍历序列，当遇到 null 字符串时，直接返回一个 null ，然后分割向左向右递归，将结点加入到 root 结点左右

这里反序列化的顺序与序列化的顺序相同

public TreeNode deserialize(String data) {
    // 这一步是为了去掉字符串左右的 [ 和 ]
    data = data.substring(1, data.length() - 1);
    // 将根据 "," 分割的数组加入到一个队列中
    Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
    return deserialize(queue);
}

private TreeNode deserialize(Queue<String> queue) {
    String value = queue.poll();
    if ("null".equals(value)) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(value));
    root.left = deserialize(queue);
    root.right = deserialize(queue);
    return root;
}

4、判断二叉树是不是平衡二叉树

4.1、题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

4.2、解题思路

如果要保证一棵树是平衡二叉树，那么需要满足以下条件

• 根节点的左子树必须是一棵平衡树
• 根节点的右子树也必须是一棵平衡树
• 根节点左右子树的高度差不饿能大于 2

在这道题中，我们需要向左右子树拿到的信息有

1. 左 / 右子树是否是一棵平衡树
2. 左右子树的高度

4.3、解题代码

• 创建一个类，这个类用于封装根节点从左右子树中获取的信息

public static class Info {        public boolean isBalanced;        public int height;    }

• 向左向右递归，让左子树和右子树也给根节点这样的信息

满足以下条件之一，那么该树为非平衡树

1. 该树的左子树不平衡
2. 该树的右子树不平衡
3. 该树的左右高度差大于 1

public static class Info {
    public boolean isBalanced;
    public int height;
    public Info (boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

public boolean isBalanced(TreeNode root) {
    return balancedInfo(root).isBalanced;
}

public Info balancedInfo (TreeNode node) {
    if (node == null) return new Info(true, 0);
    Info leftInfo = balancedInfo(node.left);
    Info rightInfo = balancedInfo(node.right);
    int leftHeight = leftInfo.height;
    int rightHeight = rightInfo.height;
    int height = Math.max(leftHeight, rightHeight) + 1;
    // 先为 isBalanced 变量设置一个初始值，即 true
    boolean isBalanced = true;
    // 如果根节点的左子树或右子树有一个不平衡，或者说它的左子树高度和右子树高度差大于 1
    if (!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftHeight - rightHeight) > 1) {
        isBalanced = false;
    }
    return new Info(isBalanced, height);
}

5、二叉树的最大距离

5.1、题目描述

给定一棵二叉树的根结点 root ，任何两个结点之间都存在距离，返回整棵二叉树的最大距离

5.2、解题思路

在以 root 为根节点的树中，最大距离与 root 可能存在两种关系

• 最大距离不经过 root 结点

这个时候，二叉树的最大距离可以在左子树的最大距离和右子树的最大距离中取最大值，即 maxDistance(root) = Math.max{maxDistance(root.left), maxDistance(root.right)}

• 最大距离需要经过 root 结点

此时二叉树的最大距离 maxDistance(root) = 二叉树左子树高度 + 二叉树右子树高度 + 1 ，其中 1 为根节点 root

• 我们需要从左右子树中获取什么信息？

1. 左右子树的高度
2. 左右子树的最大距离

5.3、解题代码

• 创建一个类，封装左右子树需要给我们返回的两个信息

public static class ChildrenInfo {
    public int maxDistance;
    public int height;
    public ChildrenInfo (int maxDistance, int height) {
        this.height = height;
        this.maxDistance = maxDistance;
    }
}

• 解题代码

public ChildrenInfo getChildrenInfo(TreeNode root) {
    if (root == null) return new ChildrenInfo(0, 0);
    ChildrenInfo leftInfo = getChildrenInfo(root.left);
    ChildrenInfo rightInfo = getChildrenInfo(root.right);
    // 最大距离怎么求？
    // 该结点的左子树最大距离、该结点右子树的最大距离和（该结点的左子树的高度 + 该结点的右子树的高度 + 1）
    // 三者的最大值即为最大距离
    int maxDistance = Math.max(
            Math.max(leftInfo.maxDistance, rightInfo.maxDistance), (leftInfo.height + rightInfo.height + 1)
    );
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    return new ChildrenInfo(maxDistance, height);
}

public int getMaxDistance(TreeNode root) {
    return getChildrenInfo(root).maxDistance;
}

6、字符串交换

6.1、题目描述

给定一个字符串 str 和一个长度 leftSize，请将 str 左侧 leftSize 部分和有部分做一个整体交换，要求使用的额外空间复杂度为 O(1)

• 示例：

输入 str = “abcdef”, leftSize = 4

输出 str =”efabcd”

6.2、解题思路

我们分为三步来完成这道题

• 将第 1 个到第 leftSize 个字符进行逆序

在上面的例子中，将 abcd 进行逆序

• 将剩下的字符作为一组，也进行逆序

在上面的例子中，将 ef 进行逆序

• 最后将整个字符串进行逆序

在上面的例子中，最后将 dcbafe 进行逆序，获得的结果是 efabcd

6.3、解题代码

• 创建一个方法，这个方法用于在数组中原地交换字符，这里使用双指针进行交换

初始时，左指针放在最左边，右指针放在最右边，然后使用一个中间变量 temp 进行交换，交换完后，左指针++，右指针–，直到左右指针相等或错开

public void reverse(char[] arr, int left, int right) {
    while (left < right) {
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

• 按照上面的解题思路，将待交换字符串分为两组，分别进行逆序后再对整个数组进行逆序

public String exchangeByGroup (String str, int leftSize) {
    if (str == null || "".equals(str.trim())) return str;
    // 先对下标为 0 - (leftSize - 1) 的分组进行逆序
    reverse(str.toCharArray(), 0, leftSize - 1);
    // 然后对下标为 leftSize - (str.length() - 1) 的分组进行逆序
    reverse(str.toCharArray(), leftSize, str.length() - 1);
    // 最后对整个字符串进行逆序
    reverse(str.toCharArray(), 0, str.length() - 1);
    return str;
}

7、将有序数组转换为二叉搜索树

7.1、题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

7.2、解题思路

• 获取数组中的中间值，以这个值作为根节点构建树
• 递归向左向右构造子树

7.3、解题代码

public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums, 0, nums.length - 1);
}


private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    int rootVal = nums[mid];
    TreeNode root = new TreeNode(rootVal);
    root.left = sortedArrayToBST(nums, left, mid - 1);
    root.right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}