二叉树day7
513. 找树左下角的值
/**
* 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 int deep = -1;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
prevOrder(root, 0);
return value;
}
private void prevOrder(TreeNode root, int depth) {
if (root == null) return;
if (root.left == null && root.right == null) {
//depth记录遍历的深度 deep记录当前记录最左值结点深度
if (depth > deep) {
deep = depth;
value = root.val;
}
}
if (root.left != null) prevOrder(root.left, depth + 1);
if (root.right != null) prevOrder(root.right, depth + 1);
}
}
//层序迭代
// class Solution {
// public int findBottomLeftValue(TreeNode root) {
// Deque queue = new LinkedList<>();
// queue.offer(root);
// int res = root.val;
// while (!queue.isEmpty()) {
// int size = queue.size();
// //每层第一个节点就是该层最左节点
// TreeNode cur = queue.poll();
// res = cur.val;
// //第一个节点子节点入队
// if (cur.left != null) queue.offer(cur.left);
// if (cur.right != null) queue.offer(cur.right);
// for (int i = 1; i < size; i++){
// //该层其他节点子节点入队
// cur = queue.poll();
// if (cur.left != null) queue.offer(cur.left);
// if (cur.right != null) queue.offer(cur.right);
// }
// }
// return res;
// }
// } 112. 路径总和
/**
* 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) {
//先放到该结点的路径和1，在放该结点
Deque113. 路径总和 II
//前序递归
class Solution {
private List> res;
private List path;
public List> pathSum(TreeNode root, int targetSum) {
res = new ArrayList<>();
if (root == null) return res;
path = new LinkedList<>();
path.add(root.val);
prevOrder(root, targetSum - root.val);
return res;
}
private void prevOrder(TreeNode root, int count) {
if (root.left == null && root.right == null && count == 0) res.add(new ArrayList<>(path));
if (root.left == null && root.right == null) return;
if (root.left != null) {
path.add(root.left.val);
prevOrder(root.left, count - root.left.val);
path.remove(path.size() - 1);
}
if (root.right != null) {
path.add(root.right.val);
prevOrder(root.right, count - root.right.val);
path.remove(path.size() - 1);
}
}
} 106. 从中序与后序遍历序列构造二叉树
//用下标划分界限 左闭右开
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
private TreeNode buildTree(int[] inorder, int ls, int le, int[] postorder, int rs, int re) {
//用前序遍历结果集判断该树是否还有结点或还有一个结点的情况
//没有节点了
if (le - ls < 1) return null;
//只有一个结点
if (le - ls == 1) return new TreeNode(inorder[ls]);
//构造子树
//后序遍历最后一个结点为根节点
int rVal = postorder[re - 1];
TreeNode root = new TreeNode(rVal);
//定义变量存储根结点在前序遍历结果中的下标
int rootIndex = 0;
//在前序遍历结果中找到根节点做为界限
for (int i = ls; i < le; i++) {
if (inorder[i] == rVal) {
rootIndex = i;
break;
}
}
//构造子树的左子树和右子树 注意区间左闭右开
root.left = buildTree(inorder, ls, rootIndex, postorder, rs, rs + (rootIndex - ls));
root.right = buildTree(inorder, rootIndex + 1, le, postorder, rs + (rootIndex - ls), re - 1);
return root;
}
}参考：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#java