广度优先搜索

本质是队列的入队与出队，先进先出

public void BFS(ArrayDeque<TreeNode> treeNodes, List<List<Integer>> result) {
    int size = treeNodes.size();
    if (size == 0) {
        return;
    }
    List<Integer> tmp = new ArrayList<>();
    for (int i = 0; i < size; i ++) {
        TreeNode treeNode = treeNodes.poll();
        tmp.add(treeNode.val);
        if (treeNode.right != null) {
            treeNodes.offer(treeNode.left);
        }
        if (treeNode.left != null) {
            treeNodes.offer(treeNode.right);
        }

    result.add(tmp);
    BFS(treeNodes, result, rowNum);
}

代码核心点：

递归：当队列为空，则退出
循环：每次递归走一个循环，循环条件为当前队列中元素个数，即每次循环开始，都是本行节点数，例如4个，一边从头poll，一边从尾offer，这个循环条件确保了下一行的不会被重复poll并扫描

【leetcode.103 二叉树锯齿形遍历】

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

该题目要求第一行正序，第二行倒序，第三行正序。。。

只需要将BFS的逻辑稍作修改，增加一个行数记录，按奇偶行数分类即可

如果是奇数，使用Dequeue.pollFirst，插入新行时使用Dequeue.offerLast，先插左，再插右
如果是偶数，使用Dequeue.pollLast，插入新行时使用Dequeue.offerFirst，先插右，再插左

这其中的一个关键是，如果是倒序遍历，插入时先插右，再插左，保证插入下一行永远都是顺序的，否则下一行倒序插入再倒序遍历，就有问题了

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayDeque<TreeNode> treeNodes = new ArrayDeque<>();
        if (root == null) {
            return new ArrayList<>();
        }
        treeNodes.add(root);
        int rowNum = 1;
        List<List<Integer>> result = new ArrayList<>();
        BFS(treeNodes, result, rowNum);
        return result;
    }

    public void BFS(ArrayDeque<TreeNode> treeNodes, List<List<Integer>> result, int rowNum) {
        int size = treeNodes.size();
        if (size == 0) {
            return;
        }
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < size; i ++) {
            if (rowNum % 2 == 0) {
                TreeNode treeNode = treeNodes.removeLast();
                tmp.add(treeNode.val);
                if (treeNode.right != null) {
                    treeNodes.addFirst(treeNode.right);
                }
                if (treeNode.left != null) {
                    treeNodes.addFirst(treeNode.left);
                }
            } else {
                TreeNode treeNode = treeNodes.removeFirst();
                tmp.add(treeNode.val);
                if (treeNode.left != null) {
                    treeNodes.addLast(treeNode.left);
                }
                if (treeNode.right != null) {
                    treeNodes.addLast(treeNode.right);
                }
            }
        }
        result.add(tmp);
        rowNum += 1;
        BFS(treeNodes, result, rowNum);
    }
}

深度优先搜索/递归

深度优先和递归是绑定在一起的，深度的本身就是一种递归

public void BFS(TreeNode root, List<Integer> result) {
    if (root == null) {
        result.add(null);
        return;
    }
    // 中序遍历
    BFS(root.left, result);
    result.add(root.val);
    BFS(root.right, result);
}

其实做递归问题就一个理念：写好边界条件，只认函数含义！

比如这个BFS函数，其边界条件就是遍历到底，root == null的场景，按照题目要求看看要不要把null加result

而BFS的含义就是遍历二叉树，因此直接调用BFS处理左子树、右子树就行了，其他的不用管

【leetcode.236 二叉树的公共最深祖先】

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // root是p和q最近公共父节点的条件是：
        //   1. p、q在root左、右孩子
        //   2. 或p、q其中一个是根，另一个是孩子
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        boolean isLeftChild = isChildOrSelf(root.left, p, q);
        boolean isRightChild = isChildOrSelf(root.right, p, q);
        
        if (isLeftChild && isRightChild) {
            return root;
        } else if (isLeftChild) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }

    }


    private boolean isChildOrSelf(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        boolean isLeftChild = isChildOrSelf(root.left, p, q);
        boolean isRightChild = isChildOrSelf(root.right, p, q);
        
        return isLeftChild || isRightChild || root.val == p.val || root.val == q.val;
    }
}

这个题的做法就是，如果是公共最深祖先，那么p和q一定在root的左右两侧，或p和q就是root

因此我们需要一个判断是否是孩子的方法，来判断root.left和root.right

而isChildOrSelf函数的边界条件就是两个：

root == null，则返回false
是左孩子，或是右孩子，或p和q是自己

因为第二个条件，那么我们直接递归左孩子和右孩子就好了，即只要认清函数的能力，然后写好边界条件，剩下的就是调用了

【leedcode.200 岛屿问题】

岛屿问题放到二叉树里面，实际上因为它可以理解为一个四叉树，即上下左右

另一个岛屿问题很经典的就是辅助数组的使用，即是否已经检查过的数组isChecked，这种数组往往只需要使用boolean数组，就可以与主问题数组一起遍历了，并且调用起来特别方便

岛屿问题的思路：遍历地块，发现地块值是1，且!isChecked，则岛屿数量+1，同时检查这个地块连接的四个方向，直到遇到非陆地停下来

public int numIslands(char[][] grid) {
    // 遍历grid，找到1，找其四边的1，找到一个存一个bool[][]，递归结束，继续遍历，遍历到存在的1，跳过
    int length = grid.length;
    int width = grid[0].length;
    boolean[][] hasChecked = new boolean[length][width];
    int result = 0;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < width; j++) {
            result += checkIsland(grid, i, j, hasChecked);
        }
    }
    return result;

}

private int checkIsland(char[][] grid, int i, int j, boolean[][] hasChecked) {
    int result = 0;
    if (!hasChecked[i][j] && grid[i][j] == '1') {
        traceIsland(grid, i, j, hasChecked);
        result += 1;
    }

    return result;
}

private void traceIsland(char[][] grid, int i, int j, boolean[][] hasChecked) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || hasChecked[i][j]) {
        return;
    } else if (grid[i][j] == '1') {
        hasChecked[i][j] = true;
    } else {
        hasChecked[i][j] = true;
        return;
    }
    traceIsland(grid, i - 1, j, hasChecked);
    traceIsland(grid, i + 1, j, hasChecked);
    traceIsland(grid, i, j - 1, hasChecked);
    traceIsland(grid, i, j + 1, hasChecked);
}

因此递归函数traceIsland的边界条件是：

四方向越界，或已经检查过
如果是岛屿，标记已检查，然后递归上下左右
如果是陆地，标记已检查，停止递归

其他问题

【leetcode105. 从前序、中序序列构造二叉树】

此问题的核心就是根据前序确定一个根，然后去中序中找这个根，然后以根为中心找到左子树、右子树节点个数，然后拿着这个个数回到前序序列中划分段落，继续找根

因此构造的独立方法中，需要传入四个端点：前序的开始index，前序的结束index，中序的开始index，中序的结束index，即从前序对应的子序列中继续找根，然后回到中序的子序列中继续划分左右子树

分别对左右子树调用这个方法

TreeNode treeNode = new TreeNode(preorder[pStartNo], 
          findRootNdoe(preorder, pLeftStartNo, pLeftEndNo, inorder, iLeftStartNo, iLeftEndNo),
          findRootNdoe(preorder, pRightStartNo, pRightEndNo, inorder, iRightStartNo, iRightEndNo));

初始条件有两个：

前序的开始index=前序的结束index，返回TreeNode左右孩子均为null即可
前序的开始index > 前序的结束index，返回null即可，这个场景不好想，为什么会有这个场景呢，是因为树有可能特别短，计算右子树时，pRightStartNo可能会超大，计算+1都超大，即原始树可能就2或1个单位

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int startNo = 0;
        int endNo = preorder.length - 1;
        TreeNode treeNode = findRootNdoe(preorder, startNo, endNo, inorder, startNo, endNo);
        return treeNode;
    }

    public TreeNode findRootNdoe(int[] preorder, int pStartNo, int pEndNo, int[] inorder, int iStartNo, int iEndNode) {
        // startNo指向的肯定是根
        if (pStartNo == pEndNo) {
            return new TreeNode(preorder[pStartNo], null, null);
        }
        if (pStartNo > pEndNo) {
            return null;
        }
        // 需要拿到xx、yy的值，通过inorder
        // 查找preorder[startNo]在inorder中的位置
        int rootIndex = selectNode(inorder, preorder[pStartNo], iStartNo, iEndNode);
        int leftChildTreeNum = rootIndex - iStartNo;
        int rightChildTreeNum = iEndNode - rootIndex;
        int pLeftStartNo = pStartNo + 1;
        int pLeftEndNo = pLeftStartNo + leftChildTreeNum - 1;
        int iLeftStartNo = iStartNo;
        int iLeftEndNo = rootIndex - 1;
        int pRightStartNo = pLeftEndNo + 1;
        int pRightEndNo = pRightStartNo + rightChildTreeNum - 1;
        int iRightStartNo = rootIndex + 1;
        int iRightEndNo = iEndNode;



        TreeNode treeNode = new TreeNode(preorder[pStartNo], findRootNdoe(preorder, pLeftStartNo, pLeftEndNo, inorder, iLeftStartNo, iLeftEndNo),
                findRootNdoe(preorder, pRightStartNo, pRightEndNo, inorder, iRightStartNo, iRightEndNo));
        return treeNode;
    }

    private int selectNode(int[] inorder, int value, int iStartNo, int iEndNode) {
        for (int i = iStartNo; i <= iEndNode; i++) {
            if (inorder[i] == value) {
                return i;
            }
        }
        return iEndNode;
    }
}

目录CONTENT

二叉树