本文主要是介绍代码随想录-算法训练营day18【二叉树05：找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客
第六章 二叉树 part05今日内容 ● 513.找树左下角的值
● 112. 路径总和 113.路径总和ii
● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树详细布置 找树左下角的值 本地递归偏难，反而迭代简单属于模板题， 两种方法掌握一下 题目链接/文章讲解/视频讲解：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 路径总和 本题 又一次设计要回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解 112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html 从中序与后序遍历序列构造二叉树 本题算是比较难的二叉树题目了，大家先看视频来理解。 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 往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY目录
0513_找树左下角的值
0112_路径总和
0113_路径总和ii
0106_从中序与后序遍历序列构造二叉树
0105_从前序与中序遍历序列构造二叉树
0513_找树左下角的值
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.LinkedList;public class _0513_找树左下角的值 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0513 {public int findBottomLeftValue(TreeNode root) {//迭代法int res = 0;if (root == null) {return res;}Deque<TreeNode> deuqe = new LinkedList<>();deuqe.offer(root);while (!deuqe.isEmpty()) {int size = deuqe.size();for (int i = 0; i < size; i++) {TreeNode poll = deuqe.poll();if (i == 0) {res = poll.val;}if (poll.left != null) {deuqe.offer(poll.left);}if (poll.right != null) {deuqe.offer(poll.right);}}}return res;}
}class Solution0513_2 {//递归法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);}
}0112_路径总和
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.ArrayList;
import java.util.Stack;public class _0112_路径总和 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0112 {public boolean hasPathSum(TreeNode root, int targetSum) {ArrayList<Integer> paths = new ArrayList<>();Boolean flag = false; //使用 Boolean包装类 来存储flag的状态traversal(root, paths, targetSum, flag);//flag不能是基本数据类型，return flag; //简化返回逻辑，直接返回flag// int[] flag = new int[1]; //使用长度为1的数组来存储flag的状态
// //Integer flag = 0; //使用 Integer包装类 来存储flag的状态
// //Boolean flag = false; //使用 Boolean包装类 来存储flag的状态
// traversal(root, paths, targetSum, flag);
// return flag[0] == 1; //简化返回逻辑}private void traversal(TreeNode root, ArrayList<Integer> paths, int targetSum, Boolean flag) {if (root == null || flag) { //如果 flag 已经为 true，则不再进行遍历return;}paths.add(root.val);if (root.left == null && root.right == null) {int sum = 0;for (int x : paths) {sum += x;}if (sum == targetSum) {flag = true;return;}}if (root.left != null) {traversal(root.left, paths, targetSum, flag);paths.remove(paths.size() - 1);}if (root.right != null) {traversal(root.right, paths, targetSum, flag);paths.remove(paths.size() - 1);}}
}class Solution0112_2 {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;}public boolean haspathsum2(TreeNode root, int targetsum) {//lc112 简洁方法if (root == null) return false; //为空退出//叶子节点判断是否符合if (root.left == null && root.right == null) return root.val == targetsum;//求两侧分支的路径和return haspathsum2(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);}
}class Solution0112_3 {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) return false;Stack<TreeNode> stack1 = new Stack<>();Stack<Integer> stack2 = new Stack<>();stack1.push(root);stack2.push(root.val);while (!stack1.isEmpty()) {int size = stack1.size();for (int i = 0; i < size; i++) {TreeNode node = stack1.pop();int sum = stack2.pop();//如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回trueif (node.left == null && node.right == null && sum == targetSum) {return true;}//右节点，压进去一个节点的时候，将该节点的路径数值也记录下来if (node.right != null) {stack1.push(node.right);stack2.push(sum + node.right.val);}//左节点，压进去一个节点的时候，将该节点的路径数值也记录下来if (node.left != null) {stack1.push(node.left);stack2.push(sum + node.left.val);}}}return false;}public boolean hasPathSum2(TreeNode root, int targetSum) {Stack<TreeNode> treeNodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();if (root == null)return false;treeNodeStack.add(root);sumStack.add(root.val);while (!treeNodeStack.isEmpty()) {TreeNode curr = treeNodeStack.peek();int tempsum = sumStack.pop();if (curr != null) {treeNodeStack.pop();treeNodeStack.add(curr);treeNodeStack.add(null);sumStack.add(tempsum);if (curr.right != null) {treeNodeStack.add(curr.right);sumStack.add(tempsum + curr.right.val);}if (curr.left != null) {treeNodeStack.add(curr.left);sumStack.add(tempsum + curr.left.val);}} else {treeNodeStack.pop();TreeNode temp = treeNodeStack.pop();if (temp.left == null && temp.right == null && tempsum == targetSum)return true;}}return false;}
}0113_路径总和ii
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;public class _0113_路径总和II {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0113 {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new ArrayList<>();if (root == null) {//非空判断return res;}List<Integer> paths = new ArrayList<>();traversal(root, targetSum, res, paths);return res;}private void traversal(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> paths) {if (root == null) {return;}paths.add(root.val);if (root.left == null && root.right == null) {int sum = paths.stream().mapToInt(Integer::intValue).sum();if (targetSum == sum) {res.add(new ArrayList<>(paths));}}if (root.left != null) {traversal(root.left, targetSum, res, paths);paths.remove(paths.size() - 1);}if (root.right != null) {traversal(root.right, targetSum, res, paths);paths.remove(paths.size() - 1);}}
}class Solution0113_2 {public List<List<Integer>> pathsum(TreeNode root, int targetsum) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;//非空判断List<Integer> path = new LinkedList<>();preOrderDfs(root, targetsum, res, path);return res;}public void preOrderDfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {path.add(root.val);if (root.left == null && root.right == null) {//遇到了叶子节点if (targetsum - root.val == 0) {//找到了和为targetSum的路径res.add(new ArrayList<>(path));}return;//如果和不为targetSum，返回}if (root.left != null) {preOrderDfs(root.left, targetsum - root.val, res, path);path.remove(path.size() - 1); //回溯}if (root.right != null) {preOrderDfs(root.right, targetsum - root.val, res, path);path.remove(path.size() - 1); //回溯}}
}class Solution0113_3 {List<List<Integer>> result;LinkedList<Integer> path;public List<List<Integer>> pathSum(TreeNode root, int targetSum) {result = new LinkedList<>();path = new LinkedList<>();travesal(root, targetSum);return result;}private void travesal(TreeNode root, int count) {if (root == null) return;path.offer(root.val);count -= root.val;if (root.left == null && root.right == null && count == 0) {result.add(new LinkedList<>(path));}travesal(root.left, count);travesal(root.right, count);path.removeLast();//回溯}
}class Solution0113_4 {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {//DFS统一迭代法List<List<Integer>> result = new ArrayList<>();Stack<TreeNode> nodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();Stack<ArrayList<Integer>> pathStack = new Stack<>();if (root == null)return result;nodeStack.add(root);sumStack.add(root.val);pathStack.add(new ArrayList<>());while (!nodeStack.isEmpty()) {TreeNode currNode = nodeStack.peek();int currSum = sumStack.pop();ArrayList<Integer> currPath = pathStack.pop();if (currNode != null) {nodeStack.pop();nodeStack.add(currNode);nodeStack.add(null);sumStack.add(currSum);currPath.add(currNode.val);pathStack.add(new ArrayList(currPath));if (currNode.right != null) {nodeStack.add(currNode.right);sumStack.add(currSum + currNode.right.val);pathStack.add(new ArrayList(currPath));}if (currNode.left != null) {nodeStack.add(currNode.left);sumStack.add(currSum + currNode.left.val);pathStack.add(new ArrayList(currPath));}} else {nodeStack.pop();TreeNode temp = nodeStack.pop();if (temp.left == null && temp.right == null && currSum == targetSum)result.add(new ArrayList(currPath));}}return result;}
}0106_从中序与后序遍历序列构造二叉树
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class _0106_从中序与后序遍历序列构造二叉树 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0106 {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;}
}class Solution0106_2 {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder.length == 0 || inorder.length == 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {if (postorderStart == postorderEnd)return null;int rootVal = postorder[postorderEnd - 1];TreeNode root = new TreeNode(rootVal);int middleIndex;for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {if (inorder[middleIndex] == rootVal)break;}int leftInorderStart = inorderStart;int leftInorderEnd = middleIndex;int rightInorderStart = middleIndex + 1;int rightInorderEnd = inorderEnd;int leftPostorderStart = postorderStart;int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);int rightPostorderStart = leftPostorderEnd;int rightPostorderEnd = postorderEnd - 1;root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);return root;}
}class Solution0106_3 {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder == null || postorder.length == 0) {return null;}TreeNode root = new TreeNode(postorder[postorder.length - 1]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = inorder.length - 1;for (int i = postorder.length - 2; i >= 0; i--) {int postorderVal = postorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.right = new TreeNode(postorderVal);stack.push(node.right);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex--;}node.left = new TreeNode(postorderVal);stack.push(node.left);}}return root;}
}0105_从前序与中序遍历序列构造二叉树
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;public class _0105_从前序与中序遍历序列构造二叉树 {
}/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution0105 {Map<Integer, Integer> map;public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {//用map保存中序序列的数值对应位置map.put(inorder[i], i);}return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); //前闭后开}public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {//参数里的范围都是前闭后开if (preBegin >= preEnd || inBegin >= inEnd) {//不满足左闭右开，说明没有元素，返回空树return null;}int rootIndex = map.get(preorder[preBegin]); //找到前序遍历的第一个元素在中序遍历中的位置TreeNode root = new TreeNode(inorder[rootIndex]); //构造结点int lenOfLeft = rootIndex - inBegin; //保存中序左子树个数，用来确定前序数列的个数root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,inorder, inBegin, rootIndex);root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,inorder, rootIndex + 1, inEnd);return root;}
}class Solution0105_2 {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}这篇关于代码随想录-算法训练营day18【二叉树05：找树左下角的值、路径总和、从中序与后序遍历序列构造二叉树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
