代码随想录算法训练营，9月12日 | 513.找树左下角的值，112. 路径总和，106.从中序与后序遍历序列构造二叉树

513.找树左下角的值
题目链接：513.找树左下角的值
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰找树左下角的值
日期：2024-09-12

想法：1.迭代：用层序遍历，遍历每层时记录下第一个节点的值，到最后一层就是要求的值；2.递归：根据最大的深度来找目标值。
Java代码如下：

//迭代
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        if(root != null) que.offer(root);
        int res = 0;
        while(!que.isEmpty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                TreeNode node = que.poll();
                if(i == 0){
                    res = node.val;
                }
                if(node.left != null){
                    que.offer(node.left);
                }
                if(node.right != null){
                    que.offer(node.right);
                }
            }
        }
        return res;
    }
}

//递归
class Solution {
    private int maxDeep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root.left == null && root.right == null) {
            if (deep > maxDeep) {
                value = root.val;
                maxDeep = deep;
            }
            return;
        }
        if (root.left != null) {
            deep++;
            findLeftValue(root.left,deep);
            deep--;
        }
        if (root.right != null) {
            deep++;
            findLeftValue(root.right,deep);
            deep--;
        }
        return;
    }
}

112. 路径总和
题目链接：112. 路径总和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰路径总和
日期：2024-09-12

想法：用减到0来判断。
Java代码如下：

class Solution {
    private boolean travel(TreeNode root, int Sum){
        if(root.left == null && root.right == null && Sum == 0) return Sum == 0;
        if(root.left != null){
            Sum -= root.left.val;
            if(travel(root.left, Sum)) return true;
            Sum += root.left.val;
        }
        if(root.right != null){
            Sum -= root.right.val;
            if(travel(root.right, Sum)) return true;
            Sum += root.right.val;
        }
        return false;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        return travel(root, targetSum - root.val);
    }
}

总结：回溯很晕，还需要点时间。

106.从中序与后序遍历序列构造二叉树
题目链接：106.从中序与后序遍历序列构造二叉树
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰从中序与后序遍历序列构造二叉树
日期：2024-09-12

想法：第一步：如果数组大小为零的话，说明是空节点了；第二步：如果不为空，那么取后序数组最后一个元素作为节点元素；第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点；第四步：切割中序数组，切成中序左数组和中序右数组；第五步：切割后序数组，切成后序左数组和后序右数组；第六步：递归处理左区间和右区间。可以设置中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)，相当于找到每一层的根。
Java代码如下：

//106.从中序与后序遍历序列构造二叉树
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0){
            return null;
        }
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    private TreeNode build(int[] inorder, int instart, int inend, int[] postorder, int poststart, int postend){
        if(postend - poststart == 0){
            return null;
        }
        int rootValue = postorder[postend - 1];
        TreeNode root = new TreeNode(rootValue);
        int i = 0;
        for(; i < inorder.length; i++){
            if(inorder[i] == rootValue){
                break;
            }
        }
        int leftinstart = instart;
        int leftiend = i;//分割点，左闭右开
        int rightinstart = i + 1;
        int rightinend = inend;

        int leftpoststart = poststart;
        int leftpostend = poststart + (i - leftinstart);//长度等于前序中的
        int rightpoststart = poststart + (i - leftinstart);//都是左闭右开
        int rightpostend = postend - 1;
        root.left = build(inorder, leftinstart, leftiend, postorder, leftpoststart, leftpostend);
        root.right = build(inorder, rightinstart, rightinend, postorder, rightpoststart, rightpostend);
        return root;
    }
}

//105. 从前序与中序遍历序列构造二叉树(思路是一样的)
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        return build(inorder, 0, inorder.length, preorder, 0, preorder.length);
    }
    private TreeNode build(int[] inorder, int instart, int inend, int[] preorder, int prestart, int preend){
        if(preend - prestart == 0){
            return null;
        }
        int rootValue = preorder[prestart];
        TreeNode root = new TreeNode(rootValue);
        int i = 0;
        for(; i < inorder.length; i++){
            if(inorder[i] == rootValue){
                break;
            }
        }
        int leftinstart = instart;
        int leftinend = i;//分割点，左闭右开
        int rightinstart = i + 1;
        int rightinend = inend;

        int leftprestart = prestart + 1;
        int leftpreend = prestart + 1 + (i - leftinstart);//长度等于前序中的
        int rightprestart = prestart + 1 +(i - leftinstart);//都是左闭右开
        int rightpreend = preend;
        root.left = build(inorder, leftinstart, leftinend, preorder, leftprestart, leftpreend);
        root.right = build(inorder, rightinstart, rightinend, preorder, rightprestart, rightpreend);
        return root;
    }
}