博客

一、513.找树左下角的值

使用的是前序遍历，所以需要用到回溯的思想。

前序遍历与后序遍历不同，它是在处理当前节点后才去搜索左右孩子，所以定义的方法不需要返回值。最后返回的值需要在类中定义，这样每个方法都可以使用到。

以下是代码部分：

public class 找树左下角的值513 {

    //记录最大的深度
    int max = 0;
    //记录最深最左的节点
    int res;

    public int findBottomLeftValue(TreeNode root) {

        if(root==null)
            return root.val;

        dfs(root, 1);
        return res;
    }

    private void dfs(TreeNode node, int depth){

        if(node.left==null && node.right==null){
            if(depth>max){
                max = depth;
                res = node.val;
            }
            return;
        }

        if(node.left!=null)
            dfs(node.left, depth+1);

        if(node.right!=null)
            dfs(node.right, depth+1);
    }

}

二、112路径之和

我自己的思路与上一个题类似，依旧是前序遍历，依旧需要额外定义一个递归方法。

但是，在看了卡哥的视频讲解后，发现其实可以不同重新定义一个方法。这里就需要用到targetSum值了：

每次遍历到一个节点后，用targetSum减去节点的值，当到叶子节点刚好减到0时，就说明符合题意。


注意一下递归方法中返回的值：

当左节点或者右节点有一个符合要求时，就返回true。

以下是代码部分：

	public boolean hasPathSum3(TreeNode root, int targetSum) {

        //如果根节点为空
        if(root == null)
            return false;

        //判断叶子节点
        if(root.left==null && root.right==null){
            if(targetSum-root.val == 0)
                return true;
        }

        //简化，不需要再判断左右节点是否为空。
        //因为如果符合要求，就在叶子节点中直接return true了，不会再遍历到空节点
        return hasPathSum3(root.left,targetSum - root.val)  || hasPathSum3(root.right, targetSum - root.val);
    }

三、113路径之和Ⅱ

这道题其实跟上一道题类似，有两个让我踩坑的地方：

1. 
   java中的参数传递都是值传递，没有引用传递。
   
2. 
   当要在list的集合中加入一个新的list时，需要new出一个list
   

                //这里，添加新的list，需要先new出一个list才行
                //res.add(list); ——>错误做法
                res.add(new ArrayList<>(list));

以下是代码部分：

public class 路径总和Ⅱ113 {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        dfs(root, targetSum);

        return res;
    }

    private void dfs(TreeNode node, int targetSum){

        if(node == null)
            return;

        if(node.left==null && node.right==null){
            //符合要求
            if(targetSum - node.val == 0){
                list.add(node.val);

                //*****
                //这里，添加新的list，需要先new出一个list才行
                //res.add(list); ——>错误做法
                res.add(new ArrayList<>(list));


                //删除刚刚加入的最后一个元素
                list.remove(list.size()-1);
            }
            return ;
        }

        list.add(node.val);

        //左右遍历
        dfs(node.left, targetSum-node.val);
        dfs(node.right, targetSum-node.val);

        list.remove(list.size()-1);
    }
}

四、106从中序与后序遍历序列构造二叉树

这道题完全没有思路，所以先看的卡哥的视频讲解。了解到了构造二叉树的

六大步骤

：

第一步：如果数组大小为零的话，说明是空节点了。

第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第五步：切割后序数组，切成后序左数组和后序右数组

第六步：递归处理左区间和右区间

以下是代码部分：

public class 从中序与后序遍历序列构造二叉树106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        //如果是空数组
        //if(postorder == null)  ——>这个是错误的写法
        if(postorder.length == 0)
            return null;

        int tmp = postorder[postorder.length-1];
        //构造一个节点
        TreeNode node = new TreeNode(tmp);
        //如果当前数组仅剩最后一个节点，直接return
        if(postorder.length==1)
            return node;

        //分割点
        int index = 0;
        //遍历中序数组，寻找分割位置
        for(;index<inorder.length;index++) {
            //找到分割位置，即当前根节点
            if (inorder[index] == tmp)
                break;
        }

        //分割中序数组
        int[] leftin = new int[index];
        for (int i = 0; i < leftin.length; i++) {
            leftin[i] = inorder[i];
        }
        int[] rightin = new int[inorder.length - index - 1];
        for (int i = 0; i < rightin.length; i++) {
            rightin[i] = inorder[index+i+1];
        }

        //分割后序数组
        int[] leftpost = new int[index];
        for (int i = 0; i < leftpost.length; i++) {
            leftpost[i] = postorder[i];
        }
        int[] rightpost = new int[inorder.length - index - 1];
        for (int i = 0; i < rightpost.length; i++) {
            rightpost[i] = postorder[index+i];
        }

        //继续通过递归方式寻找当前节点的左右孩子
        node.left = buildTree(leftin,leftpost);
        node.right = buildTree(rightin, rightpost);

        //返回当前节点
        return node;
    }

}