个人博客主页：http://myblog.nxx.nx.cn
代码GitHub地址：https://github.com/nx-xn2002/Data_Structure.git
Day17
513. 找树左下角的值
题目链接：
https://leetcode.cn/problems/find-bottom-left-tree-value/
题目描述：
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
思路：
可以用递归实现，优先选取最左侧节点，仅当左为空时，才考虑右子树，同时维护两个个变量存储最大深度和结果的值即可
代码实现：
class Solution {
int maxDepth = Integer.MIN_VALUE;
int res;
public int findBottomLeftValue(TreeNode root) {
traversal(root, 0);
return res;
}
private void traversal(TreeNode root, int depth) {
if (root.left == null && root.right == null) {
if (depth > maxDepth) {
maxDepth = depth;
res = root.val;
}
return;
}
if (root.left != null) {
traversal(root.left, depth + 1);
}
if (root.right != null) {
traversal(root.right, depth + 1);
}
}
}
112. 路径总和
题目链接：
https://leetcode.cn/problems/path-sum/
题目描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
思路：
简单使用递归实现即可，不断传入新的目标值，当当前节点时叶子节点时，判断目标值是否等于节点值即可
代码实现：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return targetSum - root.val == 0;
}
boolean left = false, right = false;
if (root.left != null) {
left = hasPathSum(root.left, targetSum - root.val);
}
if (root.right != null) {
right = hasPathSum(root.right, targetSum - root.val);
}
return left || right;
}
}
106. 从中序与后序遍历序列构造二叉树
题目链接：
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
题目描述：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
思路：
使用递归进行层层切割即可，以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
代码实现：
class Solution {
int post_idx;
int[] postorder;
int[] inorder;
Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
public TreeNode helper(int in_left, int in_right) {
if (in_left > in_right) {
return null;
}
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
int index = idx_map.get(root_val);
post_idx--;
root.right = helper(index + 1, in_right);
root.left = helper(in_left, index - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
post_idx = postorder.length - 1;
int idx = 0;
for (Integer val : inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
}