513.找树左下角的值
题目链接：513. 找树左下角的值 - 力扣（LeetCode）
题目
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
思路
这道题要找深度最大的叶子节点。
那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
代码
1 // 递归法
2 class Solution {
3 private int Deep = -1;
4 private int value = 0;
5 public int findBottomLeftValue(TreeNode root) {
6 value = root.val;
7 findLeftValue(root,0);
8 return value;
9 }
10
11 private void findLeftValue (TreeNode root,int deep) {
12 if (root == null) return;
13 if (root.left == null && root.right == null) {
14 if (deep > Deep) {
15 value = root.val;
16 Deep = deep;
17 }
18 }
19 if (root.left != null) findLeftValue(root.left,deep + 1);
20 if (root.right != null) findLeftValue(root.right,deep + 1);
21 }
22 }
1 //迭代法
2 class Solution {
3
4 public int findBottomLeftValue(TreeNode root) {
5 Queue<TreeNode> queue = new LinkedList<>();
6 queue.offer(root);
7 int res = 0;
8 while (!queue.isEmpty()) {
9 int size = queue.size();
10 for (int i = 0; i < size; i++) {
11 TreeNode poll = queue.poll();
12 if (i == 0) {
13 res = poll.val;
14 }
15 if (poll.left != null) {
16 queue.offer(poll.left);
17 }
18 if (poll.right != null) {
19 queue.offer(poll.right);
20 }
21 }
22 }
23 return res;
24 }
25 }
112. 路径总和
题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
思路
递归法: 前序遍历二叉树，记录下所有的路径，每遇到一个节点就将目标值减去节点值，如果遍历到的节点没有左右孩子则此时为路径末尾，判断值是否为0。
代码
1 class solution {
2 public boolean haspathsum(treenode root, int targetsum) {
3 if (root == null) {
4 return false;
5 }
6 targetsum -= root.val;
7 // 叶子结点
8 if (root.left == null && root.right == null) {
9 return targetsum == 0;
10 }
11 if (root.left != null) {
12 boolean left = haspathsum(root.left, targetsum);
13 if (left) { // 已经找到
14 return true;
15 }
16 }
17 if (root.right != null) {
18 boolean right = haspathsum(root.right, targetsum);
19 if (right) { // 已经找到
20 return true;
21 }
22 }
23 return false;
24 }
25 }
26
27 // lc112 简洁方法
28 class solution {
29 public boolean haspathsum(treenode root, int targetsum) {
30
31 if (root == null) return false; // 为空退出
32
33 // 叶子节点判断是否符合
34 if (root.left == null && root.right == null) return root.val == targetsum;
35
36 // 求两侧分支的路径和
37 return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
38 }
39 }
1 class solution {
2 public boolean haspathsum(treenode root, int targetsum) {
3 if (root == null) {
4 return false;
5 }
6 targetsum -= root.val;
7 // 叶子结点
8 if (root.left == null && root.right == null) {
9 return targetsum == 0;
10 }
11 if (root.left != null) {
12 boolean left = haspathsum(root.left, targetsum);
13 if (left) { // 已经找到
14 return true;
15 }
16 }
17 if (root.right != null) {
18 boolean right = haspathsum(root.right, targetsum);
19 if (right) { // 已经找到
20 return true;
21 }
22 }
23 return false;
24 }
25 }
26
27 // lc112 简洁方法
28 class solution {
29 public boolean haspathsum(treenode root, int targetsum) {
30
31 if (root == null) return false; // 为空退出
32
33 // 叶子节点判断是否符合
34 if (root.left == null && root.right == null) return root.val == targetsum;
35
36 // 求两侧分支的路径和
37 return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
38 }
39 }
113.路径总和ii
题目链接：Loading Question... - 力扣（LeetCode）
题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
思路
113.路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！
代码
1 class solution {
2 public List<List<Integer>> pathsum(TreeNode root, int targetsum) {
3 List<List<Integer>> res = new ArrayList<>();
4 if (root == null) return res; // 非空判断
5
6 List<Integer> path = new LinkedList<>();
7 preorderdfs(root, targetsum, res, path);
8 return res;
9 }
10
11 public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
12 path.add(root.val);
13 // 遇到了叶子节点
14 if (root.left == null && root.right == null) {
15 // 找到了和为 targetsum 的路径
16 if (targetsum - root.val == 0) {
17 res.add(new ArrayList<>(path));
18 }
19 return; // 如果和不为 targetsum，返回
20 }
21
22 if (root.left != null) {
23 preorderdfs(root.left, targetsum - root.val, res, path);
24 path.remove(path.size() - 1); // 回溯
25 }
26 if (root.right != null) {
27 preorderdfs(root.right, targetsum - root.val, res, path);
28 path.remove(path.size() - 1); // 回溯
29 }
30 }
31 }
1 // 解法2
2 class Solution {
3 List<List<Integer>> result;
4 LinkedList<Integer> path;
5 public List<List<Integer>> pathSum (TreeNode root,int targetSum) {
6 result = new LinkedList<>();
7 path = new LinkedList<>();
8 travesal(root, targetSum);
9 return result;
10 }
11 private void travesal(TreeNode root, int count) {
12 if (root == null) return;
13 path.offer(root.val);
14 count -= root.val;
15 if (root.left == null && root.right == null && count == 0) {
16 result.add(new LinkedList<>(path));
17 }
18 travesal(root.left, count);
19 travesal(root.right, count);
20 path.removeLast(); // 回溯
21 }
22 }
106.从中序与后序遍历序列构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
题目
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]
思路
想要用中序和后序遍历序列确定一个唯一的二叉树，就要每次以后序数组的最后一个元素为切割点，将中序数组分割成左右两份，再根据中序数组的分割情况来切割后序数组，如此反复，每次的切割点就是中间的节点。
那么代码应该怎么写呢？
说到一层一层切割，就应该想到了递归。
来看一下一共分几步：
-
第一步：如果数组大小为零的话，说明是空节点了。
-
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
-
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
-
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
-
第五步：切割后序数组，切成后序左数组和后序右数组
-
第六步：递归处理左区间和右区间
如何切割数组？
首先要切割中序数组，为什么先切割中序数组呢？
切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。
中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割。
接下来就要切割后序数组了。
首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。
后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
代码
1 class Solution {
2 Map<Integer, Integer> map; // 方便根据数值查找位置
3 public TreeNode buildTree(int[] inorder, int[] postorder) {
4 map = new HashMap<>();
5 for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
6 map.put(inorder[i], i);
7 }
8
9 return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
10 }
11
12 public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
13 // 参数里的范围都是前闭后开
14 if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
15 return null;
16 }
17 int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
18 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
19 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
20 root.left = findNode(inorder, inBegin, rootIndex,
21 postorder, postBegin, postBegin + lenOfLeft);
22 root.right = findNode(inorder, rootIndex + 1, inEnd,
23 postorder, postBegin + lenOfLeft, postEnd - 1);
24
25 return root;
26 }
27 }
105.从前序与中序遍历序列构造二叉树
题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
题目
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
思路
跟上题同理。
代码
1 class Solution {
2 Map<Integer, Integer> map;
3 public TreeNode buildTree(int[] preorder, int[] inorder) {
4 map = new HashMap<>();
5 for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
6 map.put(inorder[i], i);
7 }
8
9 return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); // 前闭后开
10 }
11
12 public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
13 // 参数里的范围都是前闭后开
14 if (preBegin >= preEnd || inBegin >= inEnd) { // 不满足左闭右开，说明没有元素，返回空树
15 return null;
16 }
17 int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的第一个元素在中序遍历中的位置
18 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
19 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数
20 root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
21 inorder, inBegin, rootIndex);
22 root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
23 inorder, rootIndex + 1, inEnd);
24
25 return root;
26 }
27 }
思考
前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
那么前序和后序可不可以唯一确定一棵二叉树呢？
前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。
标签：遍历,return,int,中序,二叉树,序列,null,root,节点 From： https://www.cnblogs.com/xpp3/p/17136074.html