代码随想录算法训练营第18天

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ans = -1;
        List<Integer> layer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        // 初始判断：树空？
        if(root != null) {
            queue.offer(root);
            queue.offer(null);  // 压入null表示隔开这一层
        }
        else return ans;
        // 遍历
        while(!queue.isEmpty()) {
            if(queue.peek() != null) {
                // 顶部非空，正在遍历这一层
                layer.add(queue.peek().val);  // 当前节点入layer
                // System.out.println(layer);
                if(queue.peek().left != null) queue.offer(queue.peek().left);  // 压入左
                if(queue.peek().right != null) queue.offer(queue.peek().right);  // 压入右
                queue.poll();  // 弹出顶
            }
            else {
                // 顶部空，这一层遍历完毕
                // System.out.println(layer);
                ans = layer.get(0);
                layer = new ArrayList<>();  // 当前layer清空
                queue.poll();  // 弹出空
                if(!queue.isEmpty()) queue.offer(null);
            }
        }
        return ans;
    }
}

class Solution {
    public boolean ans;
    public int targetSum;
    public int nowSum;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        this.ans = false;
        this.targetSum = targetSum;
        this.nowSum = 0;
        if(root != null) invert(root);
        return ans;
    }
    // 1.返回值：无
    public void invert(TreeNode node) {
        // 2.结束条件：到达叶子
        if(node.left == null && node.right == null) {
            this.nowSum += node.val;
            if(this.nowSum == this.targetSum) this.ans = true;
            this.nowSum -= node.val;
            return;
        }
        // 3.递归逻辑
        this.nowSum += node.val;
        if(node.left != null) invert(node.left);
        if(node.right != null) invert(node.right);
        this.nowSum -= node.val; // 回溯
    }
}

class Solution {
    public List<List<Integer>> ans;
    public List<Integer> path;
    public int targetSum;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        this.ans = new ArrayList<>();
        this.path = new ArrayList<>();
        this.targetSum = targetSum;
        if(root != null) invert(root);
        return ans;
    }
    // 1.返回值：无
    public void invert(TreeNode node) {
        // 2.结束条件：到达叶子
        if(node.left == null && node.right == null) {
            this.path.add(node.val);
            if(path.stream().mapToLong(Integer::intValue).sum() == this.targetSum) {
                List<Integer> copyOfPath = new ArrayList<>(path);
                this.ans.add(copyOfPath);
            }
            this.path.remove(this.path.size() - 1);
            return;
        }
        // 3.递归逻辑
        this.path.add(node.val);
        if(node.left != null) invert(node.left);
        if(node.right != null) invert(node.right);
        this.path.remove(this.path.size() - 1); // 回溯
    }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    
    }
    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
            if(inorder[middleIndex] == rootVal)
                break;
        }
 
        int leftInorderStart = inorderStart; 
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;
 
 
        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (leftInorderEnd - leftInorderStart);
        int rightPostorderStart = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
 
        return root;
    }  
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return invert(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    // 1.返回值：当前子树的根节点
    public TreeNode invert(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        // 2.结束条件：到达空（遍历数组长度为0），返回空
        if(preStart == preEnd) return null;
        // 3.递归逻辑
        // 3.1.找当前节点（中间节点）：前序的第一个必是中间节点
        TreeNode root = new TreeNode(preorder[preStart], null, null);
        // 3.2.用中间结点切分中序数组为左右两半
        int i;
        for(i = inStart; i < inEnd; i++) {
            if(inorder[i] == root.val) break;
        }
        int inLeftStart = inStart;
        int inLeftEnd = i;
        int inRightStart = i + 1;
        int inRightEnd = inEnd;
        // 3.3.用切开的中序数组长度决定前序数组怎么切（记得去掉当前前序的第一个元素，因为这个元素已经被当作中间节点拿走了）
        int preLeftStart = preStart + 1;
        int preLeftEnd = preLeftStart + (inLeftEnd - inLeftStart);
        int preRightStart = preLeftEnd;
        int preRightEnd = preEnd;
        // 3.4.用切开的数组递归，其返回值接到当前节点的左右
        root.left = invert(preorder, preLeftStart, preLeftEnd, inorder, inLeftStart, inLeftEnd);
        root.right = invert(preorder, preRightStart, preRightEnd, inorder, inRightStart, inRightEnd);
        // 3.5.返回root
        return root;
    }
}