RE：从零开始的Leetcode刷题记录

FelixMundial

2020-11-23

Leetcode 算法

# 二叉树

# 二叉树遍历

# 递归

void preorderTraversal(TreeNode root) {
  if (root == null) {
    return;
  }
  /* 是否操作root */
  preorderTraversal(root.left);
  /* 是否操作root */
  preorderTraversal(root.right);
  /* 是否操作root */
}

# 前序非递归

# 普通栈

List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  
  TreeNode node = root;
  Stack<TreeNode> stack = new Stack<>();
  
  while (true) {
    // "一路向左"：遍历至最左节点
    if (node != null) {
      res.add(node.val);
      // 栈中压入右子节点
      if (node.right != null) {
        stack.push(node.right);
      }
      node = node.left;
    } else if (!stack.isEmpty()) {
      // 从栈中获取已存储的每一个右子节点，重复循环流程
      node = stack.pop();
    } else {
      return res;
    }
  }
}

# 双端队列

List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  
  Stack<TreeNode> stack = new Stack<>();
	stack.push(root);
  
  while(!stack.isEmpty()) {
    TreeNode node = stack.pop();
    res.add(node.val);
    if (node.left != null) {
      stack.push(node.right);
    }
    if (node.right != null) {
      stack.push(node.left);
    }
  }
  return res;
}

# 中序非递归

# 普通栈

List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  
  TreeNode node = root;
  Stack<TreeNode> stack = new Stack<>();
  
  while (true) {
    // "一路向左"：遍历至最左节点
    if (node != null) {
      // 栈中压入根节点
      stack.push(node);
      node = node.left;
    } else if (!stack.isEmpty()) {
      // 从栈中获取已存储的每一个根节点，进行处理
      node = stack.pop();
      res.add(node.val);
      // 通过每一个根节点获取每一个右子节点，重复循环流程
      node = node.right;
    } else {
      return res;
    }
  }
}

# 后序非递归

# 普通栈

List<Integer> postorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  
  Stack<TreeNode> stack = new Stack<>();
  TreeNode prev = null;
  stack.push(root);
  
  while (!stack.isEmpty()) {
    // 按"根-右-左"顺序将整棵树入栈
    TreeNode node = stack.peek();
    if (/*为叶子节点*/node.left == null && node.right == null ||
        /*当前节点子节点已访问过*/prev != null && (prev == node.left || prev == node.right)) {
      prev = node.pop();
      res.add(prev.val);
    } else {
      if (node.right != null) {
        stack.push(node.right);
      }
      if (node.left != null) {
        stack.push(node.left);
      }
    }
  }
  return res;
}

# 双端队列（与前序遍历流程相同，但针对集合的所有操作倒置）

List<Integer> postorderTraversal(TreeNode root) {
  // res集合需支持双端操作
  List<Integer> res = new LinkedList<>();
  if (root == null) {
    return res;
  }
  
  Deque<TreeNode> deque = new ArrayDeque<>();
  deque.offerFirst(root);
  
  while(!deque.isEmpty()) {
    TreeNode node = deque.pollFirst();
    res.addFirst(node);
    
    if (node.right != null) {
      deque.offerFirst(node.right);
    }
    if (node.left != null) {
      deque.offerFirst(node.left);
    }
  }
  return res;
}

# DFS

# 自顶向下

向dfs()方法传递结果集并在方法内部进行结果集更新（追加），一般不返回该结果集

dfs步骤借助递归实现，在递归处理子节点返回后无其他操作

List<Integer> dfsDownwardsTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<>();
  dfs(root, res);
  return res;
}

void dfs(TreeNode root, List<Integer> res) {
  if (root == null) {
    return;
  }
  
	/* res.add(root.val); */
  dfs(root.left, res);
  /* res.add(root.val); */
  dfs(root.right, res);
	/* res.add(root.val); */ // 转化为自底向上（分治）
}

# 自底向上（分治/归并）

在分治方法内部完成“分-并”过程并返回新结果集

“分”步骤借助递归实现，在递归处理子节点返回后还需继续处理根节点与子节点间的联系

List<Integer> dfsUpwardsTraversal(TreeNode root) {
  return divideAndConquer(root);
}

List<Integer> divideAndConquer(TreeNode root) {
  List<Integer> res = new ArrayList<>();
  if (root == null) {
    return res;
  }
  
  // partition
  ListNode left = divideAndConquer(root.left);
  ListNode right = divideAndConquer(root.right);
  
  // merge
  /* res.add(root.val); */
  if (left != null) {
    res.addAll(left.val);
  }
  /* res.add(root.val); */
  if (right != null) {
    res.addAll(right.val);
  }
  /* res.add(root.val); */
  return res;
}

# BFS（层序遍历）

List<Integer> levelOrderTraverse(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();
    for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      res.add(node.val);
      if (node.left != null) {
        queue.offer(node.left);
      }
      if (node.right != null) {
        queue.offer(node.right);
      }
    }
  }
  
  return res;
}

# 104. 二叉树的最大深度 (opens new window)

DFS（自底向上）：只能采取自底向上（分治）遍历实现层数统计

# 111. 二叉树的最小深度 (opens new window)

DFS（自底向上）：

# 110. 平衡二叉树 (opens new window)

DFS（自底向上，同104）：在自底向上（分治）遍历的同时利用最大深度（是否为-1）记录当前节点“是否平衡”

# 124. 二叉树中的最大路径和 (opens new window)

DFS（自底向上，同104）：

通过左右子节点的最大贡献值计算当前节点的贡献值

每一节点的最大路径和取决于该节点值与该节点的左右子节点的贡献值之和

# 103. 二叉树的锯齿形层次遍历 (opens new window)

BFS：层序遍历中维护方向信息，每一层遍历结束后进行倒转；使用双端队列接收结果集

# 98. 验证二叉搜索树 (opens new window)

中序遍历：额外维护prev节点信息，处理当前节点时通过与prev节点比较大小实现验证

# 101. 对称二叉树 (opens new window)

BFS：在层序遍历时，每次连续弹出两个节点，并按对称节点顺序推入四个子节点；考察连续弹出的两节点是否对称

DFS（自顶向下）

# 114. 二叉树展开为链表 (opens new window)

普通迭代：

将节点右子树接入左子树的最右节点

将节点左子树接入到原右子树位置

迭代为新的右子树，重复上述步骤，直至右子树为空

前序遍历：利用遍历将节点串联成链表（通过非递归前序遍历避免每一节点原右子节点发生丢失）

后序遍历（右-左-根）：利用遍历将节点串联成链表（通过后序遍历避免每一节点原右子节点发生丢失）

# 701. 二叉搜索树中的插入操作 (opens new window)

非递归

递归

# 450. 删除二叉搜索树中的节点 (opens new window)

非递归

递归

# 105. 从前序与中序遍历序列构造二叉树 (opens new window)

DFS（自底向上）：

定位根节点

自底向上（分治）获取左右子节点串联至根节点

栈（迭代）：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--22/