代码随想录算法训练营第十六天 | 513-找树左下角的值、112-路径总和、113-路径总和Ⅱ、106-从中序与后序遍历序列构造二叉树、105-从前序与中序遍历序列构造二叉树
LeetCode513 找树左下角的值
题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/description/
文章讲解：https://programmercarl.com/0513.找树左下角的值.html
视频讲解：https://www.bilibili.com/video/BV1424y1Z7pn/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这题要找的是最后一行的最左边节点的值，其实就是要找到深度最深的最左边的叶子节点
需要类里的两个全局变量，maxDepth用来记录最大深度，result记录最大深度最左节点的数值，优先遍历左节点，确保是最左边
当遇到叶子节点时，统计当前深度，若比maxDepth记录值大则更新result为当前节点数值，注意在找最大深度的时候，递归过程中依然要使用回溯（递归回来上一层的时候，需要再把depth减一）
class Solution {int result = 0;int maxDepth = Integer.MIN_VALUE;public int findBottomLeftValue(TreeNode root) {getResult(root,1);return result;}public void getResult(TreeNode node, int depth){if(node.left == null && node.right == null){if(depth > maxDepth){result = node.val;maxDepth = depth;}return;}if(node.left != null){depth++;getResult(node.left, depth);depth--;}if(node.right != null){depth++;getResult(node.right, depth);depth--;}}
}
若使用迭代法做这题，就是采用层序遍历，每一层记录最开始遍历的那个节点的值，即为最左，遍历到最后一层即为最左下角的值
class Solution {public int findBottomLeftValue(TreeNode root) {int result = 0;if(root == null){return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size = queue.size();for(int i = 0; i < size; i++){TreeNode curNode = queue.poll();if(i == 0){result = curNode.val;}if(curNode.left != null){queue.offer(curNode.left);}if(curNode.right != null){queue.offer(curNode.right);}}}return result;}
}
LeetCode112 路径总和
题目链接：https://leetcode.cn/problems/path-sum/description/
文章讲解：https://programmercarl.com/0112.路径总和.html
视频讲解：https://www.bilibili.com/video/BV19t4y1L7CR/?vd_source=b989f2b109eb3b17e8178154a7de7a51
累加然后判断是否等于目标和，代码会比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。若最后count == 0且到达叶子节点的话，说明找到了目标和、目标路径；若遍历到了叶子节点，但count不为0，就是没找到
如果递归函数返回true，说明找到了合适的路径，直接返回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 && hasPathSum(root.left, targetSum)){return true;}if(root.right != null && hasPathSum(root.right, targetSum)){return true;}return false;}
}
LeetCode113 路径总和Ⅱ
题目链接：https://leetcode.cn/problems/path-sum-ii/description/
这题注意收割结果的时候是 result.add(new ArrayList<>(records)); ，因为直接写了 result.add(records); 而DEBUG了很久（捂脸）
class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> result = new ArrayList<>();if(root == null){return result;}List<Integer> records = new ArrayList<>();getPath(root, targetSum, records, result);return result;}public void getPath(TreeNode node, int count, List<Integer> records, List<List<Integer>> result){records.add(node.val);count -= node.val;if(node.left == null && node.right == null){if(count == 0){result.add(new ArrayList<>(records));}return;}if(node.left != null){getPath(node.left, count, records, result);records.remove(records.size()-1);}if(node.right != null){getPath(node.right, count, records, result);records.remove(records.size()-1);}}
}
LeetCode106 从中序与后序遍历序列构造二叉树
题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
文章讲解：https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html
视频讲解：https://www.bilibili.com/video/BV1vW4y1i7dn/
思想还算明了，但是代码实现起来很多细节需要处理，还是比较难的
第一步：若数组大小为0，说明为空节点，返回null
第二步：若不为空，则取后序数组最后一个元素作为节点元素
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点index
第四步：切割中序数组，切成中序左数组和中序右数组
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理当前节点的左区间和右区间
切割时始终遵循左闭右开的原则，先处理中序数组，中序左数组范围为（inorder.begin ~ inorder.begin + index），中序右数组范围为（inorder.begin + index + 1 ~ inorder.end）
接着处理后序数组，后序左数组范围为（postorder.begin ~ postorder.begin + 中序左数组大小），后序右数组范围为（postorder.begin + 中序左数组大小 ~ postorder.end - 1）
切割完以后就是接着往下递归，当前节点左右孩子
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length == 0 || inorder.length == 0){return null;}return build(inorder, 0, inorder.length, postorder, 0, postorder.length);}public TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight){if(inLeft == inRight){return null;}int value = postorder[postRight-1];TreeNode node = new TreeNode(value);int index = 0;for(; index < inRight; index++){if(inorder[index] == value){break;}}int leftInLeft = inLeft;int leftInRight = index;int rightInLeft = index + 1;int rightInRight = inRight;int leftPostLeft = postLeft;int leftPostRight = postLeft + (index - inLeft);int rightPostLeft = leftPostRight;int rightPostRight = postRight - 1;node.left = build(inorder, leftInLeft, leftInRight, postorder, leftPostLeft, leftPostRight);node.right = build(inorder, rightInLeft, rightInRight, postorder, rightPostLeft, rightPostRight);return node;}
}
LeetCode105 从前序与中序遍历序列构造二叉树
题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0 || inorder.length == 0){return null;}return build(preorder, 0, preorder.length, inorder, 0, inorder.length);}public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){if(preLeft == preRight){return null;}int value = preorder[preLeft];TreeNode node = new TreeNode(value);if(preRight - preLeft == 1){return node;}int index = 0;for(; index < inRight; index++){if(inorder[index] == value){break;}}int leftInLeft = inLeft;int leftInRight = index;int rightInLeft = index + 1;int rightInRight = inRight;int leftPreLeft = preLeft + 1;int leftPreRight = leftPreLeft + (index - inLeft);int rightPreLeft = leftPreRight;int rightPreRight = preRight;node.left = build(preorder, leftPreLeft, leftPreRight, inorder, leftInLeft, leftInRight);node.right = build(preorder, rightPreLeft, rightPreRight, inorder, rightInLeft, rightInRight);return node;}
}