首页 > 代码库 > Chapter four Breadth First Search（宽度优先搜索）

Chapter four Breadth First Search（宽度优先搜索）

2024-09-21 09:55:34   204人阅读

BFS最主要的数据结构是Queue，由LinkedList实现。

1.binary-tree-level-order-traversal（二叉树的层次遍历）

给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

BFS解法【基本模板】：

技术分享 
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return results;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            results.add(level);
        }
        return results;
    }
}
View Code

2.binary-tree-level-order-traversal-ii（二叉树的层次遍历II）

给出一棵二叉树，返回其节点值从底向上的层次遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

技术分享 
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: buttom-up level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return results;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            results.add(level);
        }
        Collections.reverse(results);
        return results;
    }
}
View Code

注意：在第1题的基础上在返回results之前利用Colllections.reverse(results)翻转一下即可。

3.binary-tree-zigzag-level-order-traversal（二叉树的锯齿形层次遍历）

给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行） 

技术分享 
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: A list of lists of integer include 
     *          the zigzag level order traversal of its nodes‘ values 
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return results;
        }
        Stack<TreeNode> curtLevel = new Stack<TreeNode>();
        Stack<TreeNode> nextLevel = new Stack<TreeNode>();
        Stack<TreeNode> temp;
        curtLevel.push(root);
        boolean normalOrder = true;
        while (!curtLevel.empty()) {
            ArrayList<Integer> curtLevelResult = new ArrayList<Integer>();
            while (!curtLevel.empty()) {
                TreeNode node = curtLevel.pop();
                curtLevelResult.add(node.val);
                if (normalOrder) {
                    if (node.left != null) {
                        nextLevel.push(node.left);
                    }
                    if (node.right != null) {
                        nextLevel.push(node.right);
                    }
                } else {
                    if (node.right != null) {
                        nextLevel.push(node.right);
                    }
                    if (node.left != null) {
                        nextLevel.push(node.left);
                    }
                }
            }
            results.add(curtLevelResult);
            temp = curtLevel;
            curtLevel = nextLevel;
            nextLevel = temp;
            normalOrder = !normalOrder;
        }
        return results;
    }
}
View Code

注意：使用Stack（栈）先进后出的特征，curtLevel和nextLevel交替使用，normalOrder变量用于标记顺序。初始时为从左至右的顺序，下一层就应该先放入左儿子，再放入右儿子。由于栈的先进后出特性，右儿子先出来。

4.convert-binary-tree-to-linked-lists-by-depth（将二叉树按照层级转化为链表）

给一棵二叉树，设计一个算法为每一层的节点建立一个链表。也就是说，如果一棵二叉树有D层，那么你需要创建D条链表。 

技术分享 
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @return a lists of linked list
     */
    public List<ListNode> binaryTreeToLists(TreeNode root) {
        // Write your code here
        List<ListNode> result = new ArrayList<ListNode>();
        if (root == null) {
            return result;
        }
        dfs(root, 1, result);
        return result;
    }
    private void dfs(TreeNode root, int depth, List<ListNode> result) {
        if (root == null) {
            return;
        }
        ListNode node = new ListNode(root.val);
        if (result.size() < depth) {
            result.add(node);
        } else {
            node.next = result.get(depth - 1);
            result.set(depth - 1, node);
        }
        dfs(root.right, depth + 1, result);
        dfs(root.left, depth + 1, result);
    }
}
View Code

注意：使用DFS！例如下图的二叉树，运行步骤为：执行dfs(1,1，result)，结果{1}；执行dfs(3,2,{1}),结果{1，3}；执行（2,2，{1,3}），结果{1，2->3}；执行（4,3，{1，2->3}）结果{1，2->3, 4}。注意到要dfs根节点的右儿子，再dfs左二子，这样才能实现左儿子->右儿子。

技术分享

5.binary-tree-serialization（二叉树的序列化和反序列化）

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

Chapter four Breadth First Search（宽度优先搜索）


联系
我们