513. 找树左下角的值
题目链接/文章讲解/视频讲解
本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下
思路
- 求最后一行最靠左侧的值。迭代法更简单。
- 如何用递归法求左下角的值？如果一直向左遍历，最左边的不一定是在最后一行。要求最后一行，就是深度最大的叶子节点，那么如何求最左侧的值？
- 本题使用前中后序都可以。因为本题中没有中节点的处理逻辑，只要优先遍历左节点就可以，能保证求到最后一行深度最大的最靠左侧的叶子节点。
-
注意概念，靠左侧不一定是左孩子，比如节点5这里是最靠左下角的
示意
伪代码
int maxDepth = INT_MIN; // 全局变量 记录最大深度
int result; // 全局变量 最大深度最左节点的数值
private int findBottomLeftValue(Treenode root){
traversal(root, 0);
return result;
}
private void traversal(TreeNode root,int depth) {
//终止条件
if(root.left == null && root.right == null){
//进行比较
if(depth > maxDepth){
maxDepth = depth;
result = root.val;
}
return;
}
//单层逻辑
if(root.left != null){
depth++;
traversal(root.left);
depth--; //这里要回溯，回溯就在递归的下面、这里要回溯是因为要回退到根节点，重新向右遍历；
}
//可以简化为if (root.left != null) findLeftValue(root.left,deep + 1); 因为实际上depth+1并没有改变depth的值
//右边遍历和逻辑和左边一样，这里不写了
if(root.right != null){
depth++;
traversal(root.right);
depth--
}
return;
//没有中序，因为不必要
}
用传参数回退的流程：
比如有这样一棵树：
example
完整流程
初始调用：findLeftValue(1, 0)
递归到左子树：findLeftValue(2, 1)
递归到更左子树：findLeftValue(4, 2)
尝试递归更左子树：findLeftValue(null, 3)，立即返回。
返回后，在第三次调用 findLeftValue(4, 2) 中继续执行：
尝试递归右子树：findLeftValue(null, 3)，立即返回。
返回后，第二次调用 findLeftValue(2, 1) 中继续执行：
尝试递归右子树：findLeftValue(null, 2)，立即返回。
返回后，第一次调用 findLeftValue(1, 0) 中继续执行：
递归到右子树：findLeftValue(3, 1)
依次类推，整个过程按照这种逻辑递归和回溯。
/**
* 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 Solution {
int maxDepth = -1;
int result = 0;
public int findBottomLeftValue(TreeNode root) {
traversal(root, 0);
return result;
}
private void traversal(TreeNode root,int depth) {
if(root == null) return;
if(root.left == null && root.right == null){
if(depth > maxDepth){
maxDepth = depth;
result = root.val;
}
}
if(root.left != null) traversal(root.left, depth + 1);
if(root.right != null) traversal(root.right, depth + 1);
}
}
路径总和
题目链接/文章讲解/视频讲解
112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。
112
思路
- 使用递归法，遍历顺序：前中后皆可，因为不涉及中节点的处理逻辑
伪代码
public boolean haspathsum(Treenode root, int targetsum){
if (root == null) return false;
return traversal(root, sum - root.val);
}
//这里是Boolean，有返回值是因为在二叉树中是找有没有某一条路径符合，
//所以只要找到一条符合的路径就原地返回，不一定所有的都要进行遍历
//直接传入目标值，遇到一个节点就减去，这样代码简洁一些
boolean traversal(TreeNode node, int count) {
//终止条件：遇到叶子节点
if (cur.left == null && cur.right == null && count == 0) return true; // 遇到叶子节点，并且计数为0，符合题目要求
if (cur.left == null && cur.right == null) return false; // 遇到叶子节点直接返回
//单层递归逻辑
if (node.left != null) { // 左
count -= node.left.val; // 递归，处理节点
if (traversal(node.left, count)) return true; //结果要继续向上返回，把true的结果返回给根节点，告诉找到了符合题意的路径
count += cur.left.val; // 回溯，撤销处理结果
}
//这里的代码可以简化为 traversal(node.left, count -= node.left.val)
// haspathsum(root.left, targetsum - root.val)
if (node.right != null) { // 右
count -= node.right.val; // 递归，处理节点
if (traversal(node.right, count)) return true;
count += node.right.val; // 回溯，撤销处理结果
}
return false;
}
/**
* 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 Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
if(root.left == null && root.right == null && targetSum == root.val) return true;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
}
113
思路
113.路径总和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 Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum){
result.clear();
path.clear();
if(root == null) return result;
path.add(root.val); // 把根节点放进路径
traversal(root, sum - root.val);
return result;
}
private void traversal(TreeNode cur, int count){
if(cur.left == null && cur.right == null && count == 0){
result.add(new ArrayList<>(path));
return;
}
if(cur.left == null && cur.right == null) return;
if(cur.left != null){
path.add(cur.left.val);
count -= cur.left.val;
traversal(cur.left, count);
count += cur.left.val;
path.remove(path.size() - 1);
}
if(cur.right != null){
path.add(cur.right.val);
count -= cur.right.val;
traversal(cur.right, count);
count += cur.right.val;
path.remove(path.size() - 1);
}
}
}
从中序与后序遍历序列构造二叉树
题目链接/文章讲解/视频讲解
本题算是比较难的二叉树题目了，大家先看视频来理解。
106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的
106
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
思路
- 后序遍历最后一个节点一定是根节点，所以中节点为3；
- 在中序遍历中，中是3，左区间就是9，右区间就是15，20，7；
- 再看后序里面，9就是左区间元素，右子树里才有[15,7,20]，最后一个元素是20，所以20一定是中间节点
- 中序再切割中间节点，只剩下15和7，所以15是左，7是右
- 大致思路：后序找到最后一个，就是中间节点，用该节点来切割中序遍历，又反过来用中序切割后序。
伪代码
private TreeNode traversal(List<Integer> inorder, List<Integer> postorder) {
//中止条件：后序数组为空
if (postorder.size() == 0) return null;
// 后序遍历数组最后一个元素，就是当前的中间节点
int rootValue = postorder.get(postorder.size() - 1);
TreeNode root = new TreeNode(rootValue);
// 叶子节点 一步优化
if (postorder.size() == 1) return root; //这里是下面单层递归中，节点的右孩子或者左孩子会接住返回的root
// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder.get(delimiterIndex) == rootValue) break; //找到切割的点，留下index，确定中序数组切割的下标值
}
// 切割中序数组 为了得到一个左中序数组和一个右中序数组
// 左闭右开区间：[0, delimiterIndex)
List<Integer> leftInorder = new ArrayList<>(inorder.subList(0, delimiterIndex));
// [delimiterIndex + 1, end)
List<Integer> rightInorder = new ArrayList<>(inorder.subList(delimiterIndex + 1, inorder.size()));
// postorder 舍弃末尾元素
postorder.remove(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
List<Integer> leftPostorder = new ArrayList<>(postorder.subList(0, leftInorder.size()));
// [leftInorder.size(), end)
List<Integer> rightPostorder = new ArrayList<>(postorder.subList(leftInorder.size(), postorder.size()));
root.left = traversal(leftInorder, leftPostorder);
root.right = traversal(rightInorder, rightPostorder);
return root;
}
public TreeNode buildTree(List<Integer> inorder, List<Integer> postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return null;
return traversal(inorder, postorder);
}
中序和前序
- 中序：左中右，前序，中左右，用前序里确定的中去中序中分割
/**
* 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 Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0) return null;
List<Integer> inorderList = new ArrayList<>();
for (int num : inorder) {
inorderList.add(num);
}
List<Integer> postorderList = new ArrayList<>();
for (int num : postorder) {
postorderList.add(num);
}
return traversal(inorderList, postorderList);
}
private TreeNode traversal(List<Integer> inorder, List<Integer> postorder) {
if(postorder.size() == 0) return null;
int rootValue = postorder.get(postorder.size() - 1);
TreeNode root = new TreeNode(rootValue);
if(postorder.size() == 1) return root;
int index;
for(index = 0; index < inorder.size(); index++){
if(rootValue == inorder.get(index)) break;
}
List<Integer> leftInorder = new ArrayList<>(inorder.subList(0, index));
List<Integer> rightInorder = new ArrayList<>(inorder.subList(index+1, inorder.size()));
postorder.remove(postorder.size()-1);
List<Integer> leftPostorder = new ArrayList<>(postorder.subList(0, leftInorder.size()));
List<Integer> rightPostorder = new ArrayList<>(postorder.subList(leftInorder.size(), postorder.size()));
root.left = traversal(leftInorder, leftPostorder);
root.right = traversal(rightInorder, rightPostorder);
return root;
}
}
