代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树

简介: 代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树

1. LeetCode  513. 找树左下角的值

1.1 思路

  1. 运用迭代法层序遍历很简单,就最后一层第一个。以下讲解递归法
  2. 在这题只要我们求深度最大的叶子节点,就一定是在最后一行。
  3. 那么问题是最后一行怎么求第一个元素呢?这题前中后序都是可以的,“根左右”、“左根右”、“左右根”,因为这题没有“根节点”的处理逻辑的,只需要先遍历左即可,而不处理“根”那“左”就是第一个遍历的,那么一旦得到深度最大的节点,那优先遍历“左”,得到的就是最后一行第一个节点。
  4. 我们需要定义全局变量maxDepth记录最大深度,value记录节点的值
  5. 递归函数的参数和返回值:参数TreeNode,depth表示当前遍历的深度,因为操作的是全局变量,不用返回值
  6. 终止条件:遍历到叶子节点就是终止条件(left==null&&right==null)即左右孩子均为空,找到后就要比较判断了,depth是否比maxDepth大,如果大就更新maxDepth的值为depth,value更新为当前节点的数值。这步的操作只会记录到这一层第一个节点的值,因为depth和maxDepth的判断只会进行第一次
  7. 单层递归的逻辑:向左遍历,如果左孩子不为空就先给depth++,然后递归函数(root.left,depth),然后回溯,回溯要给depth--。这里为什么要--,因为处理完左孩子回溯后就要到右孩子了对吧,遍历右孩子时depth又++了,而右节点的深度和左节点是一样的,所以要--。不懂可以看视频的10分钟开始。
  8. 遍历完左侧又到向右遍历,如果右孩子不为空就如同上面向左遍历的操作

1.2 代码

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }
    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        if (root.left != null) findLeftValue(root.left,deep + 1);
        if (root.right != null) findLeftValue(root.right,deep + 1);
    }
}

2. LeetCode 112. 路径总和113. 路径总和 II

2.1 思路

  1. 本题依然是前中后序都可以,因为不涉及根节点的处理
  2. 递归函数的参数和返回值:为什么需要boolean返回值?因为这题是要找到一条符合的路径即可,没必要遍历全部的节点,因此需要返回值,并且是boolean;参数是TreeNode,计数器count,这个count的用法是目标值-节点的值,遇到一个减一个,如果到叶子节点的时候count==0,那就说明路径符合
  3. 终止条件:遇到叶子节点就要判断了,if(node.left==null&&node.right==null&&count==0)就说明叶子节点的时候count为0,就是路径了,true。if(node.left==null&&node.right==null&&count!=0)就说明不是对应路径
  4. 单层递归逻辑:向左遍历,如果左孩子不为空就先,count减去左孩子的值,然后向左递归传入(左孩子,count),因为这个函数返回的是布尔值,如果判断是返回true,那就说明已经找到路径了,那就return true,如果判断是返回false,那就回溯,count加上原来左孩子的值,为什么要加回来?因为返回false说明这条路径不对,要向右递归的时候值应该是原来的值。这部分不懂可以从视频的11分钟开始看。
  5. 向右遍历同上面向左遍历的逻辑

2.2 代码

//112. 路径总和
class Solution {
    private boolean traversal(TreeNode cur, int count) {
        if (cur.left == null && cur.right == null && count == 0) return true; // 遇到叶子节点,并且计数为0
        if (cur.left == null && cur.right == null) return false; // 遇到叶子节点直接返回
        if (cur.left != null) { // 左
            count -= cur.left.val; // 递归,处理节点;
            if (traversal(cur.left, count)) return true;
            count += cur.left.val; // 回溯,撤销处理结果
        }
        if (cur.right != null) { // 右
            count -= cur.right.val; // 递归,处理节点;
            if (traversal(cur.right, count)) return true;
            count += cur.right.val; // 回溯,撤销处理结果
        }
        return false;
    }
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        return traversal(root, sum - root.val);
    }
}
//113. 路径总和 II
class Solution {
    private List<List<Integer>> result;
    private List<Integer> path;
    private void traversal(TreeNode cur, int count) {
        if (cur.left == null && cur.right == null && count == 0) { // 遇到了叶子节点且找到了和为sum的路径
            result.add(new ArrayList<>(path));
            return;
        }
        if (cur.left == null && cur.right == null) return; // 遇到叶子节点而没有找到合适的边,直接返回
        if (cur.left != null) { // 左 (空节点不遍历)
            path.add(cur.left.val);
            count -= cur.left.val;
            traversal(cur.left, count);    // 递归
            count += cur.left.val;        // 回溯
            path.remove(path.size() - 1); // 回溯
        }
        if (cur.right != null) { // 右 (空节点不遍历)
            path.add(cur.right.val);
            count -= cur.right.val;
            traversal(cur.right, count);   // 递归
            count += cur.right.val;       // 回溯
            path.remove(path.size() - 1); // 回溯
        }
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        result = new ArrayList<>();
        path = new ArrayList<>();
        if (root == null) return result;
        path.add(root.val); // 把根节点放进路径
        traversal(root, sum - root.val);
        return result;
    }
}

3. LeetCode 106. 从中序与后序遍历序列构造二叉树105. 从前序与中序遍历序列构造二叉树

3.1 思路

  1. 我们要确定一个节点的值,这个节点就在于"中",所以我们要明确遍历的顺序
  2. 中序是左中右,后序是左右中,这说明后序里的最后一个元素就是中,而这个元素就是二叉树的根节点了,那又看中序遍历里,以这个元素为中,左右的元素就分别说左子树和右子树了,然后再看后序遍历,就可以分出左右子树了,从这里又可以看出左右子树的"中"是那个了,又可以看回中序遍历确定以某个元素为"中"的左右子树了,以此类推
  3. 递归函数的参数和返回值:返回值是一个节点,参数是两个数组,中序和后序
  4. 终止条件:后序数组为0就说明已经没有节点了,就return null
  5. 单层递归的逻辑:找到切割点,nodeVal=postorder[postorder.length-1];node=new TreeNode(nodeVal);如果(后序数组的长度==)就是只有一个节点,那就是遍历到叶子节点了,就return这个节点就可以了。
  6. 记录上述返回的切割点,然后遍历中序数组,如果找到了这个切割点就把这个点的下标记录起来,然后就是切中序数组,为了得到一个左中序数组和一个右中序数组
  7. 然后说切后序数组,拿着左中序数组的大小去切后序数组的左区间,剩下的就是右区间,就得到一个左后序和右后序的数组
  8. 然后就是递归了,左子树=travel(左中序数组,左后序数组),右子树=travel(右中序数组,右后序数组)
  9. 最后就返回root
  10. 中序和前序构造二叉树同理。但是前序和后序不可以,前序是“中左右”后序是“左右中”,可以知道“中”分别是在第一个和最后一个,关键是“左右”的区间不知道,左区间和右区间的分割点找不到,中序遍历的关键就是可以找到左右区间的间隔

3.2 代码

//106.从中序与后序遍历序列构造二叉树
class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}
//105.从前序与中序遍历序列构造二叉树
class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 参数里的范围都是前闭后开
        if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定前序数列的个数
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
                            inorder, inBegin, rootIndex);
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);
        return root;
    }
}
相关文章
|
17天前
|
数据采集 监控 安全
厂区地图导航制作:GIS技术与路径导航算法融合
在智能化、数字化时代,GIS技术为厂区的运营管理带来了革命性变化。本文探讨了如何利用GIS技术,通过数据采集、地图绘制、路径规划、位置定位和信息查询等功能,打造高效、精准的智能厂区地图导航系统,提升企业的竞争力和管理水平。
22 0
厂区地图导航制作:GIS技术与路径导航算法融合
|
21天前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
16 2
|
21天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
11 0
|
21天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
10 0
|
21天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
10 0
|
21天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
21天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
12 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2