找树左下角的值
本题递归偏难，反而迭代简单属于模板题， 两种方法掌握一下
题目链接/文章讲解/视频讲解：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
// class Solution {
// public int findBottomLeftValue(TreeNode root) {
// int value = 0;
// Queue<TreeNode> queue = new LinkedList<>();
// if(root != null) queue.offer(root);
// while(!queue.isEmpty()){
// int size = queue.size();
// int i = 0;
// while(i < size){
// TreeNode cur = queue.poll();
// if(i == 0) value = cur.val;
// if(cur.left != null) queue.offer(cur.left);
// if(cur.right != null) queue.offer(cur.right);
// i ++;
// }
// }
// return value;
// }
// }
// 递归法
class Solution {
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);
}
}
路径总和
本题 又一次涉及到回溯的过程，而且回溯的过程隐藏的还挺深，建议先看视频来理解
112. 路径总和，和 113. 路径总和ii 一起做了。 优先掌握递归法。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
class Solution {
boolean flag = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
List<TreeNode> list = new LinkedList<>();
boolean res = dbs(root, list, targetSum);
return res;
}
public boolean dbs(TreeNode root, List<TreeNode> list, int targetSum){
list.add(root);
if(root.left == null && root.right == null){
int sum = 0;
for(TreeNode node : list){
sum += node.val;
}
if(sum == targetSum) flag = true;
return flag;
}
if(root.left != null){
dbs(root.left, list, targetSum);
list.removeLast();
}
if(root.right != null){
dbs(root.right, list, targetSum);
list.removeLast();
}
return flag;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
List<TreeNode> list = new LinkedList<>();
boolean res = dbs(root, list, targetSum);
return res;
}
public boolean dbs(TreeNode root, List<TreeNode> list, int targetSum){
boolean flag = false;
boolean l = false;
boolean r = false;
list.add(root);
if(root.left == null && root.right == null){
int sum = 0;
for(TreeNode node : list){
sum += node.val;
}
if(sum == targetSum) flag = true;
return flag;
}
if(root.left != null){
l = dbs(root.left, list, targetSum);
list.removeLast();
}
if(root.right != null){
r = dbs(root.right, list, targetSum);
list.removeLast();
}
return flag || l || r;
}
}
public boolean dbs(TreeNode root, List<TreeNode> list, int targetSum){
list.add(root);
if(root.left == null && root.right == null){
int sum = 0;
for(TreeNode node : list){
sum += node.val;
}
if(sum == targetSum) return true;
}
if(root.left != null){
if(dbs(root.left, list, targetSum)) return true;
list.removeLast();
}
if(root.right != null){
if(dbs(root.right, list, targetSum)) return true;
list.removeLast();
}
return false;
}
}
路径总和2：
从中序与后序遍历序列构造二叉树
本题算是比较难的二叉树题目了，大家先看视频来理解。
106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树 一起做，思路一样的
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0) return null;
int rootval = postorder[postorder.length - 1];
TreeNode root = new TreeNode(rootval);
if(postorder.length == 1) return root;
int index = 0;
for(int i = 0; i < inorder.length; i ++){
if(inorder[i] == rootval){
index = i;
break;
}
}
int[] leftInorder = sub (inorder, 0 ,index);
int[] rightInorder = sub (inorder, index + 1 ,inorder.length);
int[] leftPostorder = sub (postorder, 0 ,leftInorder.length);
int[] rightPostorder = sub (postorder, leftInorder.length, postorder.length-1);
root.left = buildTree(leftInorder, leftPostorder);
root.right = buildTree(rightInorder, rightPostorder);
return root;
}
public int[] sub(int[] array, int start, int end){
int[] res = new int[end - start];
int r = 0;
for(int i = start; i < end; i ++){
res[r ++] = array[i];
}
return res;
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0) return null;
int rootval = preorder[0];
TreeNode root = new TreeNode(rootval);
if(preorder.length == 1) return root;
int index = 0;
for(int i = 0; i < inorder.length; i ++){
if(inorder[i] == rootval){
index = i;
break;
}
}
int[] leftInorder = sub (inorder, 0 ,index);
int[] rightInorder = sub (inorder, index + 1, inorder.length);
int[] leftPreorder = sub (preorder, 1 ,leftInorder.length + 1);
int[] rightPreorder = sub (preorder, leftInorder.length + 1, preorder.length);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
public int[] sub(int[] array, int start, int end){
int[] res = new int[end - start];
int r = 0;
for(int i = start; i < end; i ++){
res[r ++] = array[i];
}
return res;
}
}
