算法训练营 day18 二叉树 找树左下角的值 路径总和 从中序与后序遍历构建二叉树

找树的左下角

513. 找树左下角的值 - 力扣（LeetCode）

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

递归法

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

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

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

2. 确定终止条件

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

3. 确定单层递归的逻辑

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

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

层序遍历

class Solution {public int findBottomLeftValue(TreeNode root) {int result = 0;Queue que = new LinkedList<>();TreeNode node;if (root == null) return root.val;que.add(root);while (!que.isEmpty()) {int size = que.size();for (int i = 0; i < size; i++) {node = que.poll();if (i == 0) result=node.val;if (node.left!=null) que.add(node.left);if (node.right!=null) que.add(node.right);}}return result;}
}

路径总和

112. 路径总和 - 力扣（LeetCode）

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

递归法

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

参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。

2. 确定终止条件

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

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

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

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

3. 确定单层递归的逻辑

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

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

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root==null) return false;if (root.left==null&&root.right==null) return root.val==targetSum;return hasPathSum(root.left,targetSum- root.val)||hasPathSum(root.right,targetSum-root.val);}
}

迭代法

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {Stack st = new Stack<>();Stack nums = new Stack<>();if (root==null) return false;st.push(root);nums.push(root.val);TreeNode node;int sum;while(!st.isEmpty()){node = st.pop();sum = nums.pop();if (node.left==null&&node.right==null&&sum==targetSum){return true;}if (node.left!=null){st.push(node.left);nums.push(sum+node.left.val);}if (node.right!=null){st.push(node.right);nums.push(sum+node.right.val);}}return false;}
}

再来一题

113. 路径总和 II - 力扣（LeetCode）

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

class Solution {
List> result;LinkedList path;public List> 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(); // 回溯}
}

从中序与后序遍历构建二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

• 第一步：如果数组大小为零的话，说明是空节点了。
• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
• 第五步：切割后序数组，切成后序左数组和后序右数组
• 第六步：递归处理左区间和右区间

class Solution {Map 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;}
}