Breadth First Search - Githubissues

xiedaxia1hao commented 3 years ago

例题列表：

通常我们需要遍历树，有两种方法：BFS和DFS。

当问题需要我们一层一层遍历树的时候，BFS的优点就体现出来了。通常我们需要用一个Queue来保存该树当前这个level的所有node，所以BFS的空间复杂度一般都是O(W)，W代表该树在某一层中的最大node数量。

BFS有以下两种写法，一种是用迭代的方式，一种是用递归的方式，在本section中，两种方式我都会去写一遍。

NOTE: 通常迭代的话，我们会用queue去保存某一level的node数量，这样的空间复杂度就是O(n)，但是特殊情况下，题目会要求我们用constant space解题，这个时候我们就要用到O(1)的方式来BFS。

xiedaxia1hao commented 3 years ago

BFS迭代模版

102. 二叉树的层序遍历

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

对于BFS的模版，我们可以按以下思路分成五步：

把root放进新建好的一个queue里。
持续迭代直到我们的queue中元素变成空。
对于每次迭代，我们先将当前queue的size保存下来，即为我们当前这一层的node总个数。
我们将该size的node从queue中取出，然后保存在储存当前层元素的list内。
取出的同时，我们将该node的左右子节点push到queue中。
如果queue不是空，我们重复步骤3。

该题代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for(int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);
                if(currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if(currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            res.add(currentLevel);
        } 
        return res;
    }
}

Time Complexity: O(N), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.
Space Complexity: O(N)

与该题类似的在leetcode上还有一道题。

107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

该题和上面一题几乎是一样的。只是在遍历完当前这一层后，我们将当前层的node插入到res的最前面，而不是最后面。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                currentLevel.add(curr.val);
                if(curr.left != null) {
                    queue.offer(curr.left);
                }
                if(curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            // THE ONLY DIFFERENCE
            res.add(0, currentLevel);
        }
        return res;
    }
}

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

该题和前面的题基本一样，唯一的不同是对于偶数层的遍历我们是从左往右遍历，奇数层的遍历我们是从右往左遍历。这个只要设置一个变量level就行了，在插入currentLevel前对其进行判断，如果是偶数，则将当前的数插到list的最后面，不然查到list的最前面。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();

                // DIFFERENCE
                if(level % 2 == 0) {
                    currentLevel.add(curr.val);
                } else {
                    currentLevel.add(0, curr.val);
                }

                if(curr.left != null) {
                    queue.offer(curr.left);
                }
                if(curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            level++;
            res.add(currentLevel);
        }
        return res;
    }
}

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

解法和之前一样。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            double levelSum = 0;
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelSum += curr.val;
                if(curr.left != null) {
                    queue.offer(curr.left);
                }
                if(curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            res.add(levelSum/size);
        }
        return res;
    }
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。

该题和之前的题目稍微有点区别，当我们要寻找二叉树的最小深度的时候，我们只需要在前序遍历的过程中，发现某个节点的左右子节点都是null，即可返回当前depth。

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int depth = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if(curr.left == null && curr.right == null) {
                    return depth;
                }
                if(curr.left != null) {
                    queue.offer(curr.left);
                }
                if(curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

Grokking里面有一题是寻找level order successor的，题目如下：

Given a binary tree and a node, find the level order successor of the given node in the tree. The level order successor is the node that appears right after the given node in the level order traversal.

该题是要找到某个指定元素的右边节点的值，一共可以分为两种情况：

该元素右边的节点在同一个level (example 2)。
该元素右边的节点在下一个level (example 3)。

但是不管该元素右边的节点在不在一个level上，我们在level order遍历的方式遍历到指定key的时候，都已经将该key的两个子节点加入到queue中了（该key同level右边的节点在上一层遍历的时候就已经被加入到queue里了）。所以我们只要找到了key之后，退出while循环即可。

class LevelOrderSuccessor {
  public static TreeNode findSuccessor(TreeNode root, int key) {
    if (root == null)
      return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      TreeNode currentNode = queue.poll();
      // insert the children of current node in the queue
      if (currentNode.left != null)
        queue.offer(currentNode.left);
      if (currentNode.right != null)
        queue.offer(currentNode.right);

      // break if we have found the key
      if (currentNode.val == key)
        break;
    }

    return queue.peek();
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(9);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    TreeNode result = LevelOrderSuccessor.findSuccessor(root, 12);
    if (result != null)
      System.out.println(result.val + " ");
    result = LevelOrderSuccessor.findSuccessor(root, 9);
    if (result != null)
      System.out.println(result.val + " ");
  }
}

199. Binary Tree Right Side View

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

该题和上面的题目基本一致，要注意的是，因为我们要的是右视图，如果我们从左向右遍历的话，最右边的元素在queue的最后面，当我们要提取最右边的元素时，复杂度是O(n)。所以，为了降低复杂度，我们可以在每个level从右往左遍历，这样我们只要在每个level遍历前，取该queue的peek值（即为当前level的最右边的值），然后往res加进行了，这一步的复杂度就可以降到O(1)。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            // at the begining of the each level, we add the first element in the queue to our res.
            // NOTE: here we add the right child first rather than left child. 
            res.add(queue.peek().val);
            for(int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();

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

                if(curr.left != null) {
                    queue.offer(curr.left);
                }
            }
        }
        return res;
    }
}

xiedaxia1hao commented 3 years ago

BFS模版 O(1) Space

116. Populating Next Right Pointers in Each Node

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

Followup: You may only use constant extra space.

该题如果用模版写的话，虽然达不到follow up的要求，但是可以很快的写出来，如下：

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            Node prevNode = null;
            for(int i = 0; i < size; i++) {
                Node currNode = queue.poll();
                if(prevNode != null) {
                    prevNode.next = currNode;
                }
                prevNode = currNode; 
                if(currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if(currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
        }
        return root;
    }
}

但是如果需要我们用constant space来解这道题的话，就要求我们在不使用queue的情况下来对树进行遍历。代码如下：

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }

        Node levelStart = root;
        Node curr = null;

        while(levelStart != null) {
            curr = levelStart;
            while(curr != null) {
                if(curr.left != null) {
                    curr.left.next = curr.right;
                }
                if(curr.right != null && curr.next != null) {
                    curr.right.next = curr.next.left;
                }
                curr = curr.next;
            }
            levelStart = levelStart.left;
        }
        return root;
    }
}

这一题在grokking上有个followup，我们要把每个节点都与其next节点connect起来。

Connect All Level Order Siblings

这题和上题原理类似，只是我们这时候需要一个while loop外的全局prevNode来代替上一题的while loop内的prevNode。

class ConnectAllSiblings {
  public static void connect(TreeNode root) {
    TreeNode prevNode = null;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
      TreeNode currNode = queue.poll();
      if(prevNode != null) {
        prevNode.next = currNode;
      }
      prevNode = currNode;
      if(currNode.left != null) {
        queue.offer(currNode.left);
      }
      if(currNode.right != null) {
        queue.offer(currNode.right);
      }
    }
  }
}

xiedaxia1hao / leetcode_pattern

Breadth First Search #21

NOTE: 通常迭代的话，我们会用queue去保存某一level的node数量，这样的空间复杂度就是O(n)，但是特殊情况下，题目会要求我们用constant space解题，这个时候我们就要用到O(1)的方式来BFS。

BFS迭代模版

BFS模版 O(1) Space