1.树的遍历

广度优先遍历

  2. public int bfs(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         Deque<TreeNode> queue = new ArrayDeque<>();
  7.         queue.offer(root);
  8.         int ans = 0;
  9.         while (!queue.isEmpty()) {
  10.             int size = queue.size();
  11.             while (size > 0) {
  12.                 TreeNode node = queue.poll();
  13.                 if (node.left != null) {
  14.                     queue.offer(node.left);
  15.                 }
  16.                 if (node.right != null) {
  17.                     queue.offer(node.right);
  18.                 }
  19.                 size--;
  21.             }
  22.             ans++;
  23.         }
  24.         return ans;
  25.     }

深度优先遍历

  2.     public static void dfs(Node treeNode) { 
  3.         if (treeNode == null) { 
  4.             return; 
  5.         } 
  6.         // 遍历节点 
  7.         process(treeNode) 
  8.         // 遍历左节点 
  9.         dfs(treeNode.left); 
  10.         // 遍历右节点 
  11.         dfs(treeNode.right); 
  12.     } 
  15.     public static void dfsWithStack(Node root) { 
  16.     if (root == null) { 
  17.         return; 
  18.     } 
  20.     Stack<Node> stack = new Stack<>(); 
  21.     // 先把根节点压栈 
  22.     stack.push(root); 
  23.     while (!stack.isEmpty()) { 
  24.         Node treeNode = stack.pop(); 
  25.         // 遍历节点 
  26.         process(treeNode) 
  28.         // 先压右节点 
  29.         if (treeNode.right != null) { 
  30.             stack.push(treeNode.right); 
  31.         } 
  33.         // 再压左节点 
  34.         if (treeNode.left != null) { 
  35.             stack.push(treeNode.left); 
  36.         } 
  37.     } 
  38. }

翻转二叉树

  • 只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树

    // 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
  // base case
  if (root == null) {
      return null;
  }

  /**** 前序遍历位置 ****/
  // root 节点需要交换它的左右子节点
  TreeNode tmp = root.left;
  root.left = root.right;
  root.right = tmp;

  // 让左右子节点继续翻转它们的子节点
  invertTree(root.left);
  invertTree(root.right);

  return root;
}

    根据前序，中序，后序 生成树

根据后序和中序生成二叉树，核心思想是通过前序/后序找到根，再根据中序的根左右生成左右子树
image.png

TreeNode build(int[] inorder, int inStart, int inEnd,
               int[] postorder, int postStart, int postEnd) {

    if (inStart > inEnd) {
        return null;
    }
    // root 节点对应的值就是后序遍历数组的最后一个元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }
    // 左子树的节点个数
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(inorder, inStart, index - 1,
                        postorder, postStart, postStart + leftSize - 1);

    root.right = build(inorder, index + 1, inEnd,
                        postorder, postStart + leftSize, postEnd - 1);
    return root;
}

二维数组dfs

image.png

记忆化dfs

public class longestIncreasingPath {
    /**
     * dirs用于移动当前数字
     */
    private static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private static int m, n;

    public static void main(String[] args) {
        int[][] param = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        longestIncreasingPath(param);
    }

    public static int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(matrix, i, j, dp));
            }
        }
        return res;
    }

    public static int dfs(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) return dp[i][j];
        for (int[] dir : dirs) {
            int row = i + dir[0];
            int col = j + dir[1];
            if (row >= 0 && row < m && col >= 0 && col < n && matrix[i][j] < matrix[row][col]){
                dp[i][j] = Math.max(dp[i][j],dfs(matrix,row,col,dp)+1);
            }
        }
        return dp[i][j];
    }
}