十四 BFS DFS 二分查找 DLR LDR LRD - 图1

1 BFS（ 127 ）

广度优先遍历的最重要的数据结构是队列（queue），利用的就是先进先出的特性

如上图所示：对于广度优先遍历来说，遍历的流程如下所示：

  • 1加入队列中，1出队列，将1的左节点2，右节点加入队列中
  • 2出队列，将2的左节点4，右节点5加入队列
  • 3出队列，将3的左节点6，右节点7加入队列
  • 4出队列，4的左右节点都为空
  • 5出队列，5的左右节点都为空
  • 6出队列，6的左右节点都为空
  • 7出队列，7的左右节点都为空
  1. public void BFS(TreeNode node) {
  2.     if(node == null) return;
  3.     // 好像也可以使用ArrayDeque
  4.     // Queue<TreeNode> queue = new ArrayDeque<>();
  5.     Queue<TreeNode> queue = new LinkedList<>();
  6.     queue.add(node);
  7.     while(queue.peek() != null) {
  8.         TreeNode res = queue.poll();
  9.         sout(res.val);
  10.         if(res.left != null) {
  11.             queue.add(res.left);
  12.         }
  13.         if(res.right != null) {
  14.             queue.add(res.right);
  15.         }
  16.     }      
  17. }

2 DFS

深度优先遍历使用的是Stack的先进后出的特性

如上图所示：对于广度优先遍历来说，遍历的流程如下所示：

  • 将节点1入栈，出栈访问右左子节点，将右节点3，左节点2入栈
  • 节点2出栈，访问右左子节点，将右节点5，左节点4入栈
  • 节点4出栈，4的孩子为空，没有入栈操作
  • 节点5出栈，5的孩子为空，没有入栈操作
  • 节点3出栈，访问右左子节点，将右节点7，左节点6入栈
  • 节点6出栈，6的孩子为空，没有入栈操作
  • 节点7出栈，7的孩子为空，没有入栈操作
  1. public void DFS(TreeNode node) {
  3.     if(node == null) return;
  4.     Stack<TreeNode> st = new Stack<>();
  5.     st.push(node);
  6.     while(st.peek() != null) {
  7.         TreeNode res = st.pop();
  8.         sout(res.val);
  9.         if(res.right != null) {
  10.             st.push(res.right);
  11.         }
  12.         if(res.left != null) {
  13.             st.push(res.left);
  14.         }
  15.     }
  16. }

131.分割回文串

3 二分查找

  1. end = (end + start) / 2;    // 这样写会导致越界的情况产生
  2. end = start + (end - start) /2         // 避免越界的情况产生

5 LDR(中序遍历的实现)

LC：验证二叉搜索树

中序遍历：

  1. public boolean isValidBST(TreeNode root) {
  2.     Deque<TreeNode> stack = new LinkedList<>();
  3.     long preOrder = Long.MIN_VALUE;
  4.     while(!stack.isEmpty() || root != null) {
  5.         while(root != null) {
  6.             stack.push(root);
  7.             root = root.left;
  8.         }
  9.         root = stack.pop();
  10.         if(root.val <= preOrder) return false;
  11.         preOrder = root.val;
  12.         root = root.right;
  13.     }
  14. }

递归实现：

  1. public boolean isValidBST(TreeNode root) {
  2.     return recursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
  3. }
  5. public boolean recursion(TreeNode node, Long min, Long max) {
  6.     // 判断条件
  7.     ...
  8.     return recursion(node.left, min, node.val) && recursion(node.right, node.val, max);
  9. }