热门面试题第14天|Leetcode 513找树左下角的值 112 113 路径总和 105 106 从中序与后序遍历序列构造二叉树 （及其扩展形式）以一敌二

找树左下角的值

本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下

题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

我们来分析一下题目：在树的最后一行找到最左边的值。

首先要是最后一行，然后是最左边的值。

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。

如果对二叉树深度和高度还有点疑惑的话，请看：110.平衡二叉树 (opens new window)。

所以要找深度最大的叶子节点。

那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

1.确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。

本题还需要类里的两个全局变量，maxDepth用来记录最大深度，result记录最大深度最左节点的数值。

private int maxDepth = Integer.MIN_VALUE;private int result;public void traversal(TreeNode root, int depth)

2.确定终止条件

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

代码如下：

 if (root.left == null && root.right == null) {if (depth > maxDepth) {maxDepth = depth;result = root.val;}return;}

3.确定单层递归的逻辑

在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

if (root.left != null) {depth++;traversal(root.left, depth);depth--; // 回溯}if (root.right != null) {depth++;traversal(root.right, depth);depth--; // 回溯}}

我们来看完整代码

class Solution {private int maxDepth = Integer.MIN_VALUE;private int result;public void traversal(TreeNode root, int depth) {if (root.left == null && root.right == null) {if (depth > maxDepth) {maxDepth = depth;result = root.val;}return;}if (root.left != null) {depth++;traversal(root.left, depth);depth--; // 回溯}if (root.right != null) {depth++;traversal(root.right, depth);depth--; // 回溯}}public int findBottomLeftValue(TreeNode root) {traversal(root, 0);return result;}
}

路径总和

本题 又一次涉及到回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解

112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

1.确定递归函数的参数和返回类型

本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？

如图所示：

图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。

所以代码如下：

bool traversal(treenode* cur, int count)   // 注意函数的返回类型

2.确定终止条件

首先计数器如何统计这一条路径的和呢？

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。

如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。

如果遍历到了叶子节点，count不为0，就是没找到。

递归终止条件代码如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回

3.确定单层递归的逻辑

因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。

递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

if (cur->left) { // 左count -= cur->left->val; // 递归，处理节点;if (traversal(cur->left, count)) return true;count += cur->left->val; // 回溯，撤销处理结果
}
if (cur->right) { // 右count -= cur->right->val;if (traversal(cur->right, count)) return true;count += cur->right->val;
}
return false;

我们来看完整代码

class Solution {private boolean traversal(TreeNode cur, int count) {if (cur.left == null && cur.right == null && count == 0) {return true;  // 遇到叶子节点，并且计数为0}if (cur.left == null && cur.right == null) {return false;  // 遇到叶子节点直接返回}if (cur.left != null) {  // 左count -= cur.left.val;  // 递归，处理节点if (traversal(cur.left, count)) return true;count += cur.left.val;  // 回溯，撤销处理结果}if (cur.right != null) {  // 右count -= cur.right.val;  // 递归，处理节点if (traversal(cur.right, count)) return true;count += cur.right.val;  // 回溯，撤销处理结果}return false;}public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;return traversal(root, sum - root.val);}
}

注意，我们在调用的时候用的是 traversal(root, sum - root.val)， sum - root.val代表的是还需要寻找的count值

我们来看一道类似的

路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！

我们只需要用集合去存储数组，最后输出就行

我们来看代码

class Solution {private List<List<Integer>> result = new ArrayList<>();private List<Integer> path = new ArrayList<>();// 递归函数不需要返回值，因为我们要遍历整个树private void traversal(TreeNode cur, int count) {if (cur.left == null && cur.right == null && count == 0) { // 遇到了叶子节点且找到了和为sum的路径result.add(new ArrayList<>(path));return;}if (cur.left == null && cur.right == null) return; // 遇到叶子节点而没有找到合适的边，直接返回if (cur.left != null) { // 左 （空节点不遍历）path.add(cur.left.val);count -= cur.left.val;traversal(cur.left, count);    // 递归count += cur.left.val;         // 回溯path.remove(path.size() - 1);  // 回溯}if (cur.right != null) { // 右 （空节点不遍历）path.add(cur.right.val);count -= cur.right.val;traversal(cur.right, count);   // 递归count += cur.right.val;        // 回溯path.remove(path.size() - 1);  // 回溯}return;}public List<List<Integer>> pathSum(TreeNode root, int sum) {result.clear();path.clear();if (root == null) return result;path.add(root.val); // 把根节点放进路径traversal(root, sum - root.val);return result;}
}

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

本题算是比较难的二叉树题目了，大家先看视频来理解。

106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的

题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

流程如图：

 

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

• 第一步：如果数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

不难写出如下代码：（先把框架写出来）

TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {// 第一步if (postorder.size() == 0) return NULL;// 第二步：后序遍历数组最后一个元素，就是当前的中间节点int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 叶子节点if (postorder.size() == 1) return root;// 第三步：找切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 第四步：切割中序数组，得到 中序左数组和中序右数组// 第五步：切割后序数组，得到 后序左数组和后序右数组// 第六步root->left = traversal(中序左数组, 后序左数组);root->right = traversal(中序右数组, 后序右数组);return root;
}

我们进行切割的时候要先切割中序再切割后序，因为只有确定了中序的左右有几个元素，我们才可以在后序遍历里面定位

注意切割的时候需要记住中序左右数组定位需要+1，要跳过中的位置

我们来看完整代码

class Solution {private TreeNode traversal(int[] inorder, int inorderBegin, int inorderEnd, int[] preorder, int preorderBegin, int preorderEnd) {// 如果是空区间，返回nullif (preorderBegin == preorderEnd) return null;// 从前序遍历的第一个元素获取根节点的值int rootValue = preorder[preorderBegin];TreeNode root = new TreeNode(rootValue);// 如果是叶子节点，直接返回if (preorderEnd - preorderBegin == 1) return root;// 在中序遍历中找到根节点的位置int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;// 切割前序数组// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)int leftPreorderBegin = preorderBegin + 1;int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);int rightPreorderEnd = preorderEnd;// 递归构建左右子树root.left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);root.right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {if (inorder.length == 0 || preorder.length == 0) return null;// 参数遵循左闭右开的原则return traversal(inorder, 0, inorder.length, preorder, 0, preorder.length);}
}

 我们来看一个相关的题目

这道题我们是从前序，中序来遍历 

主要修改点：

1. 函数参数顺序：

   • 修改了 buildTree 方法的参数顺序，从 (inorder, postorder) 改为 (preorder, inorder)
   • 相应地修改了 traversal 方法的参数顺序

2. 根节点位置：

   • 后序遍历中根节点在最后：postorder[postorder.length - 1]
   • 前序遍历中根节点在最前：preorder[0]

3. 数组切割方式：

   • 后序数组切割：leftPostorder 从 0 开始，rightPostorder 到倒数第二个元素结束
   • 前序数组切割：leftPreorder 从第二个元素(索引1)开始，rightPreorder 到最后一个元素

4. 递归调用：

   • 修改了递归调用的参数顺序，确保传入正确的前序和中序数组

我们只要在这个基础上进行修改，就可以实现效果，我们来看代码

class Solution {private TreeNode traversal(int[] inorder, int[] preorder) {// 如果前序数组为空，返回空节点if (preorder.length == 0) return null;// 前序遍历数组第一个元素，就是当前的根节点int rootValue = preorder[0];TreeNode root = new TreeNode(rootValue);// 叶子节点if (preorder.length == 1) return root;// 找到中序遍历的切割点int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.length; delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左闭右开区间：[0, delimiterIndex)int[] leftInorder = Arrays.copyOfRange(inorder, 0, delimiterIndex);// [delimiterIndex + 1, end)int[] rightInorder = Arrays.copyOfRange(inorder, delimiterIndex + 1, inorder.length);// 切割前序数组// 依然左闭右开，注意这里使用了左中序数组大小作为切割点// [1, 1+leftInorder.length) 注意这里从1开始，因为0是根节点int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftInorder.length);// [1+leftInorder.length, end)int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftInorder.length, preorder.length);root.left = traversal(leftInorder, leftPreorder);root.right = traversal(rightInorder, rightPreorder);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {if (inorder.length == 0 || preorder.length == 0) return null;return traversal(inorder, preorder);}
}