深度优先遍历和广度优先遍历

深度优先遍历(DFS)和广度优先遍历(BFS)是两种遍历或搜索树和图的方法,常用于,呃,面试中……

深度优先遍历(DFS:Depth First Search)

DFS的遍历顺序又分为三种。下面以N代表当前结点,L代表左侧子结点,R代表右侧子结点。

  • 先序(preorder):先处理当前结点,然后对子结点从左向右处理。NLR,从上向下,从左向右
  • 中序(inorder):先处理左侧子结点,然后处理当前结点,最后处理右侧子结点。LNR,左–>当前–>右
  • 后序(postorder):先从左向右处理子结点,然后处理当前结点。LRN,从下向上,从左向右

如果把表达式放入二叉树,那么先序遍历的结果是前缀表示法(波兰表示法,Polish Notation),中序遍历的结果是中缀表示法,后序遍历的结果是后缀表示法(逆波兰表示法,Reverse Polish Notation)。

DFS的特点天然地适合使用递归的方法实现。三种顺序仅仅通过改变处理程序片段的位置就能实现,十分简单易行。用循环来实现的话,就得自己维护一个栈,而且实现起来也比较麻烦。

private void dfsInorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理左子结点
    if (node.left != null) {
        dfsInorder(node.left);
    }

    // 处理本结点
    handle(node);

    // 处理右子结点
    if (ndoe.right != null) {
        dfsInorder(node.right);
    }
}

private void dfsPreorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理本结点
    handle(node);

    // 处理子结点
    if (node.left != null) {
        dfsPreorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPreorder(node.right);
    }
}

private void dfsPostorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理子结点
    if (node.left != null) {
        dfsPostorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPostorder(node.right);
    }

    // 处理本结点
    handle(node);
}

循环的方法:估计面试时不会要求做这个吧?其中,前序比较容易,而中序比较难,后序本来更难,但鉴于它与先序的对称性,可以把结果按先序(但是改为从右向左)压入栈中,再反向逐个弹出即可。

public void dfsPreorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        handle(node);

        if (node.right!= null) {
            stack.push(node.right);
        }

        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

public void dfsInorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Node node = root;

    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            handle(node);
            node = node.right;
        }
    }
}

public void dfsPostorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Deque<Node> reversedStack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        reversedStack.push(node);

        if (node.left != null) {
            stack.push(node.left);
        }

        if (node.right != null) {
            stack.push(node.right);
        }
    }

    while (!reversedStack.isEmpty()) {
        handle(reversedStack.pop());
    }
}

广度优先遍历(BFS:Breadth First Search)

BFS的访问顺序一般是从左向右,从上向下,一层一层地处理。一般用循环通过某种容器(queue、stack、set等)来实现。

public void bfs(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        handle(node);

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

有时候在做BFS时,需要在处理完每一层后,都做一些其他的处理。这种情况下,可以在while循环中再套一个循环来实现:

public void bfsPerLevel(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int count = 0;

    while (!queue.isEmpty()) {
        int n = queue.size();

        for (int i = 0; i < n; ++i) {
            Node node = queue.poll();
            handle(node);

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        // 此处加入处理完当前层后的代码
        log.info(">>> end of level {}", count++);
    }
}

一般来说,递归跟栈相关,所以对于DFS这种递归属性的算法,可以在循环中用栈来实现。而对于BFS这种跟栈没关系的算法,一般人就会认为不能用递归实现。但实际上还是有办法做到的:

private void recursiveBfsHelper(List<Node> nodeList) {
    if (nodeList.isEmpty()) {
        return;
    }

    List<Node> nextList = new ArrayList<>();

    for (Node node : nodeList) {
        handle(node);

        if (node.left != null) {
            nextList.add(node.left);
        }

        if (node.right != null) {
            nextList.add(node.right);
        }
    }

    recursiveBfsHelper(nextList);
}

public void recursiveBfs(Node root) {
    recursiveBfsHelper(Collections.singletonList(root));
}

DFS算法实现起来简短方便(用递归的话),因此十分适合在面试中使用。但有些问题则需要用到BFS,比如求迷宫最短路径问题(因为逐层扫描直到找到解为止,这个解一定是最优解(或最优解之一),这里的最优解是路径最短的意思。

例题:二叉树的序列化和反序列化

将二叉树序列化为一个字符串,并将字符串反序列化为二叉树。

  • 需要产生压缩的结果,否则对于只有右子树的二叉树,结果会过长。
  • 由于上述要求,用DFS比较恰当,因为产生的结果便于反序列化。
    // 序列化

    // DFS preorder
    private void dfs(TreeNode root, StringBuilder sb) {
        sb.append(",");

        if (root != null) {
            sb.append(root.val);
            dfs(root.left, sb);
            dfs(root.right, sb);
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder(root.val);
        dfs(root.left, sb);
        dfs(root.right, sb);

        return sb.toString();
    }

    // 反序列化

    private TreeNode dfs(Queue<String> queue) {
        TreeNode root = null;

        if (!queue.isEmpty()) {
            String s = queue.poll();

            if (!s.equals("")) {
                root = new TreeNode(Integer.parseInt(s));
                root.left = dfs(queue);
                root.right = dfs(queue);
            }
        }

        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        Queue<String> queue = Arrays.stream(data.split(",", -1)
                .collect(Collectors.toCollection(LinkedList::new));

        return dfs(queue);
    }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注