算法训练营day18

本文主要是介绍算法训练营day18，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - - 一、找树左下角的值
    - 二、路径总和1 & 2
    - - 从路径总和1 & 2体会什么情况下递归需要返回值，什么时候不需要返回值
      - 路径总和1
      - 初始递归
      - DFS
      - BFS
      - 路径总和2
    - 三、从中序与后序遍历序列构造二叉树
    - 四、从前序和中序遍历序列构造二叉树

一、找树左下角的值

参考链接513. 找树左下角的值 - 力扣（LeetCode）

二叉树的最深最左侧的节点的值，涉及到最深 -> 联想到层序遍历

BFS

class Solution {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> d = new ArrayDeque<>();d.addLast(root);int ans = 0;while (!d.isEmpty()) {int sz = d.size();ans = d.peek().val;while (sz-- > 0) {TreeNode poll = d.pollFirst();if (poll.left != null) d.addLast(poll.left);if (poll.right != null) d.addLast(poll.right);}}return ans;}
}

DFS

class Solution {int max, ans;public int findBottomLeftValue(TreeNode root) {dfs(root, 1);return ans;}void dfs(TreeNode root, int depth) {if (root == null) return ;if (depth > max) {max = depth; ans = root.val;}//左侧先执行dfs方法，如果最后一行存在多个节点，那么左侧的节点必定先执行//那么当执行到右侧的时候由于 depth == max，最先记录的永远是最左边的节点dfs(root.left, depth + 1);dfs(root.right, depth + 1);}
}

二、路径总和1 & 2

从路径总和1 & 2体会什么情况下递归需要返回值，什么时候不需要返回值

路径总和1

初始递归

   class Solution {public boolean hasPathSum(TreeNode root, int sum) {// 如果根节点为空，直接返回falseif (root == null) return false;// 如果当前节点是叶子节点（即左右子节点都为空），检查路径和是否等于目标值if (root.left == null && root.right == null) {return sum == root.val;}// 如果当前节点不是叶子节点，递归地在左子树和右子树中查找路径// 路径和等于目标值减去当前节点的值return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

DFS

  class Solution {
public boolean hasPathSum(TreeNode root, int sum) {// 如果根节点为空，直接返回falseif (root == null) return false;// 调用深度优先搜索（DFS）函数，查找是否存在一条从根节点到叶子节点的路径，使得路径上的节点值之和等于给定的目标值return dfs(root, sum, root.val);
}private boolean dfs(TreeNode root, int target, int pathSum) {// 如果当前节点为空，直接返回falseif (root == null) return false;// 如果路径和等于目标值，并且当前节点是叶子节点（即左右子节点都为空），返回trueif (pathSum == target && root.left == null && root.right == null) {return true;}// 初始化左右子树的标志位为falseboolean leftFlag = false, rightFlag = false;// 如果左子节点不为空，递归地在左子树中查找路径，路径和等于当前路径和加上左子节点的值if (root.left != null) {leftFlag = dfs(root.left, target, pathSum + root.left.val);}// 如果右子节点不为空，递归地在右子树中查找路径，路径和等于当前路径和加上右子节点的值if (root.right != null) {rightFlag = dfs(root.right, target, pathSum + root.right.val);}// 如果左子树或右子树中存在满足条件的路径，返回true，否则返回falsereturn leftFlag || rightFlag;
}

BFS

  class Solution {
public boolean hasPathSum(TreeNode root, int sum) {// 如果根节点为空，直接返回falseif (root == null) return false;// 创建一个队列，用于广度优先搜索（BFS）Deque<Pair<TreeNode, Integer>> queue = new LinkedList<>();// 将根节点和它的值作为一个对（Pair）添加到队列中queue.offer(new Pair<>(root, root.val));// 当队列不为空时，继续循环while (!queue.isEmpty()) {// 从队列中取出一个对Pair<TreeNode, Integer> pair = queue.poll();// 获取对中的节点和路径和TreeNode node = pair.getKey();int pathSum = pair.getValue();// 如果当前节点是叶子节点（即左右子节点都为空），并且路径和等于目标值，返回trueif (node.left == null && node.right == null && pathSum == sum) {return true;}// 如果左子节点不为空，将左子节点和当前路径和加上左子节点的值作为一个对添加到队列中if (node.left != null) {queue.offer(new Pair<>(node.left, pathSum + node.left.val));}// 如果右子节点不为空，将右子节点和当前路径和加上右子节点的值作为一个对添加到队列中if (node.right != null) {queue.offer(new Pair<>(node.right, pathSum + node.right.val));}}// 如果遍历完所有节点都没有找到满足条件的路径，返回falsereturn false;
}

路径总和2

参考链接113. 路径总和 II - 力扣（LeetCode）

先序遍历 + 路径记录

class Solution {LinkedList<List<Integer>> res = new LinkedList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {recur(root, targetSum);return res;}void recur(TreeNode root, int tar) {if (root == null) return;path.add(root.val);tar -= root.val;if (tar == 0 && root.left == null && root.right == null)res.add(new LinkedList<Integer>(path));recur(root.left, tar);recur(root.right, tar);path.removeLast();}
}

三、从中序与后序遍历序列构造二叉树

class Solution {Map<Integer, Integer> map;  // 方便根据数值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {// 参数里的范围都是前闭后开if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树return null;}int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数root.left = findNode(inorder, inBegin, rootIndex,postorder, postBegin, postBegin + lenOfLeft);root.right = findNode(inorder, rootIndex + 1, inEnd,postorder, postBegin + lenOfLeft, postEnd - 1);return root;}
}

四、从前序和中序遍历序列构造二叉树

注，本文方法只适用于“无重复节点值”的二叉树。

为了提升效率，本文使用哈希表 dic 存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1) 。

class Solution {int[] preorder;HashMap<Integer, Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i = 0; i < inorder.length; i++)dic.put(inorder[i], i);return recur(0, 0, inorder.length - 1);}TreeNode recur(int root, int left, int right) {if (left > right) return null;                          // 递归终止TreeNode node = new TreeNode(preorder[root]);          // 建立根节点int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树node.left = recur(root + 1, left, i - 1);              // 开启左子树递归node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归return node;                                           // 回溯返回根节点}
}