剑指Offer之Java算法习题精讲N叉树的遍历及数组与字符串

前言

N叉树是一种特殊的树结构，其中每个节点可以包含零个或多个子节点。在这篇文章中，我们将讨论如何遍历N叉树，并提供一些示例。

N叉树的遍历

前序遍历

前序遍历的过程是先访问根节点，然后递归地访问每个子树。

在N叉树中，前序遍历的代码实现如下:

public void preOrder(Node root) {
    if (root == null) {
        return;
    }
    System.out.println(root.val);
    for (Node child : root.children) {
        preOrder(child);
    }
}

后序遍历

后序遍历的过程是先递归地访问每个子树，然后访问根节点。

在N叉树中，后序遍历的代码实现如下:

public void postOrder(Node root) {
    if (root == null) {
        return;
    }
    for (Node child : root.children) {
        postOrder(child);
    }
    System.out.println(root.val);
}

层序遍历

层序遍历是按照从上到下、从左到右的顺序遍历树的节点。

在N叉树中，层序遍历的代码实现如下:

public void levelOrder(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            System.out.println(node.val);
            for (Node child : node.children) {
                queue.offer(child);
            }
        }
    }
}

数组与字符串

数组的查找

在Java中，可以使用循环或二分查找算法来查找数组中的元素。

循环实现：

public int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

二分查找实现：

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

字符串的操作

在Java中，可以使用String类提供的方法来操作字符串，例如获取字符串长度、截取子串、替换字符串、转换大小写等。

public int getLength(String str) {
    return str.length();
}

public String getSubString(String str, int start, int end) {
    return str.substring(start, end);
}

public String replace(String str, String oldStr, String newStr) {
    return str.replace(oldStr, newStr);
}

public String toUpperCase(String str) {
    return str.toUpperCase();
}

public String toLowerCase(String str) {
    return str.toLowerCase();
}

示例说明

第一组示例

假如现在有一棵N叉树如下：

      1
    / | \
   2  3  4
  / \    |
 5   6   7

通过前序遍历的方式访问这棵树，输出结果应该是：1 2 5 6 3 4 7

Node root = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);

root.children = Arrays.asList(node2, node3, node4);
node2.children = Arrays.asList(node5, node6);

preOrder(root);
// 输出结果：1 2 5 6 3 4 7

第二组示例

假如现在有一个数组[1, 3, 5, 7, 9, 11, 13]，要查找其中数字5的位置。

使用循环实现查找，代码如下：

int[] nums = {1, 3, 5, 7, 9, 11, 13};
int target = 5;

int index = search(nums, target);
System.out.println(index);
// 输出结果：2

总结

本文讲解了N叉树的遍历以及数组与字符串的相关操作，涵盖了具体的实现代码和示例说明。这些内容对于Java程序员来说是非常基础且重要的知识点，希望大家可以掌握好这些技能，提高自己的编程水平。