代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

本文主要是介绍代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、513.找树左下角的值

题目描述： 给定一个二叉树，在树的最后一行找到最左边的值。

1.递归法

1. 确定递归函数的参数和返回值
   参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。
2. 确定终止条件
   当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
3. 确定单层递归的逻辑
   在找最大深度的时候，递归的过程中依然要使用回溯

class Solution {private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root,0);return value;}private void findLeftValue (TreeNode root,int deep) {if (root == null) return;if (root.left == null && root.right == null) {if (deep > Deep) {value = root.val;Deep = deep;}}if (root.left != null) findLeftValue(root.left,deep + 1);if (root.right != null) findLeftValue(root.right,deep + 1);}
}

二、112. 路径总和

题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

1.递归法

1. 确定递归函数的参数和返回类型
   参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
2. 确定终止条件
   不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
   如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
   如果遍历到了叶子节点，count不为0，就是没找到。
3. 确定单层递归的逻辑
   因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
   递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

class solution {public boolean haspathsum(treenode root, int targetsum) {if (root == null) {return false;}targetsum -= root.val;// 叶子结点if (root.left == null && root.right == null) {return targetsum == 0;}if (root.left != null) {boolean left = haspathsum(root.left, targetsum);if (left) {// 已经找到return true;}}if (root.right != null) {boolean right = haspathsum(root.right, targetsum);if (right) {// 已经找到return true;}}return false;}
}

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

题目描述： 根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。

1.递归法

1. 如果数组大小为零的话，说明是空节点了。
2. 如果不为空，那么取后序数组最后一个元素作为节点元素。
3. 找到后序数组最后一个元素在中序数组的位置，作为切割点。
4. 割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）。
5. 切割后序数组，切成后序左数组和后序右数组。
6. 递归处理左区间和右区间。

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;}
}

---

这篇关于代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---