day18 打卡513.找树左下角的值 112. 路径总和 113.路径总和ii 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
513.找树左下角的值
1.我的想法：使用层次遍历，每次把每个层的第一个元素压进栈。最后把最后一个元素弹出来，就是最下面一层的最左边的元素。
class Solution {
public int findBottomLeftValue(TreeNode root) {
if (root == null) return -1;
Queue<TreeNode> que = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
que.offer(root);
int size = 1;
while (!que.isEmpty()) {
size = que.size();
int start = size;
while (size>0) {
TreeNode cur = que.poll();
if (start == size) {
// 把每一层的第一个元素压进栈
stack.push(cur);
}
if (cur.left != null) que.offer(cur.left);
if (cur.right != null) que.offer(cur.right);
size--;
}
}
if (!stack.isEmpty()) {
return stack.pop().val;
}
return -1;
}
}
2.递归法。视频链接
class Solution {
private int maxDepth = -1;
private int result;
public int findBottomLeftValue(TreeNode root) {
if (root == null) return -1;
result = root.val;
traversal(root, 1);
return result;
}
public void traversal(TreeNode cur, int depth) {
if (cur.left == null && cur.right == null) {
if (maxDepth < depth) {
maxDepth = depth;
result = cur.val;
}
return;
}
if (cur.left != null) {
depth++;
traversal(cur.left, depth);
depth--;
}
if (cur.right != null) {
depth++;
traversal(cur.right, depth);
depth--;
}
}
}
112. 路径总和
1.递归法。需要注意的是hasPathSum中调用getPathSum的第二位初始的sum。一开始我设置了0，一直不对，应该是当前节点的val要加上去。因为进入方法后都是加减回溯左右节点的值。而根节点是一定在里面的。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
return getPathSum(root, root.val, targetSum);
}
public boolean getPathSum(TreeNode cur, int nowSum, int targetSum) {
if (cur.left == null && cur.right == null) {
return nowSum == targetSum;
}
if (cur.left != null) {
nowSum += cur.left.val;
if(getPathSum(cur.left, nowSum, targetSum)) {
// 已经存在一条符合要求的路径了，不需要再去回溯了
return true;
}
nowSum -= cur.left.val;
}
if (cur.right != null) {
nowSum += cur.right.val;
if (getPathSum(cur.right, nowSum, targetSum)) {
// 已经存在一条符合要求的路径了，不需要再去回溯了
return true;
}
nowSum -= cur.right.val;
}
return false;
}
}
113.路径总和ii
1.跟前一题目，思路一致。但是要注意在result.add(new LinkedList<>(list));这里不能写成result.add(list);因为加的是list的引用地址，而list到最后都是[root.val]。要重新复制一个新的对象。
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) return result;
List<Integer> list = new LinkedList<>();
list.add(root.val);
getPathSum(root, root.val, targetSum, list);
return result;
}
public void getPathSum(TreeNode cur, int nowSum, int targetSum, List<Integer> list) {
if (cur.left == null && cur.right == null) {
if (nowSum == targetSum) {
result.add(new LinkedList<>(list));
}
return;
}
if (cur.left != null) {
nowSum += cur.left.val;
list.add(cur.left.val);
getPathSum(cur.left, nowSum, targetSum, list);
nowSum -= cur.left.val;
list.remove(list.size()-1);
}
if (cur.right != null) {
nowSum += cur.right.val;
list.add(cur.right.val);
getPathSum(cur.right, nowSum, targetSum, list);
nowSum -= cur.right.val;
list.remove(list.size()-1);
}
}
}
106.从中序与后序遍历序列构造二叉树
1.根据视频来的思路写的，但是性能不好。
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 如果后序数组没有元素，返回null
if (postorder.length == 0) return null;
// 后序元素最后一个元素是中间节点
int rootVal = postorder[postorder.length-1];
TreeNode rootNode = new TreeNode(rootVal);
// 叶子节点，左子树和右子树都没有
if (postorder.length == 1) return rootNode;
// 遍历中序，找到中间节。即切割点
int inIndexLeft = 0;
for ( ; inIndexLeft<inorder.length ; inIndexLeft++) {
if (inorder[inIndexLeft] == rootVal) {
break;
}
}
// 分割中序数组的左右子树的数组
int[] inorderLeft = new int[inIndexLeft];
int[] inorderRight = new int[inorder.length-inIndexLeft-1];
int inIndexRight = 0;
for (int i = 0 ; i<inorder.length ; i++) {
if (i<inIndexLeft) {
inorderLeft[i] = inorder[i];
} else if (i>inIndexLeft){
inorderRight[inIndexRight++] = inorder[i];
}
}
// 分割后序数组的左右子树的数组
int[] postorderLeft = new int[inorderLeft.length];
int[] postorderRight = new int[inorderRight.length];
int postIndexRight = 0;
for (int i = 0 ; i<postorder.length-1 ; i++) {
if (i<inIndexLeft) {
postorderLeft[i] = postorder[i];
} else {
postorderRight[postIndexRight++] = postorder[i];
}
}
rootNode.left = buildTree(inorderLeft, postorderLeft);
rootNode.right = buildTree(inorderRight, postorderRight);
return rootNode;
}
}
105.从前序与中序遍历序列构造二叉树
1.还是按照上面的106思路来的，但是性能不好。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 如果前序数组没有的话，返回null
if (preorder.length == 0) return null;
// 取到前序遍历的第一个元素，就是中间节点
int rootVal = preorder[0];
TreeNode root = new TreeNode(rootVal);
// 如果前序数组只有一个元素，就是叶子节点
if (preorder.length == 1) return root;
// 中序数组里面找到中间节点的下标
int inorderIndex = 0;
for ( ; inorderIndex<inorder.length ; inorderIndex++) {
if (inorder[inorderIndex] == rootVal) {
break;
}
}
// 中序数组分割成左右子树
int[] inorderLeft = new int[inorderIndex];
int[] inorderRight = new int[inorder.length-inorderIndex-1];
int inorderRightIndex = 0;
for (int i = 0 ; i<inorder.length ; i++) {
if (i<inorderIndex) {
inorderLeft[i] = inorder[i];
} else if (i>inorderIndex) {
inorderRight[inorderRightIndex++] = inorder[i];
}
}
// 前序数组分割成左右子树
int[] preorderLeft = new int[inorderLeft.length];
int[] preorderRight = new int[inorderRight.length];
int preorderLeftIndex = 0;
int preorderRightIndex = 0;
for (int i = 1; i<preorder.length ; i++) {
if (i<=inorderIndex) {
preorderLeft[preorderLeftIndex++] = preorder[i];
} else {
preorderRight[preorderRightIndex++] = preorder[i];
}
}
// 返回root的左节点和右节点
root.left = buildTree(preorderLeft, inorderLeft);
root.right = buildTree(preorderRight, inorderRight);
return root;
}
}