代码随想录算法训练营第十八天 | 力扣 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;
    }
}
相关文章
|
6天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
9天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
28 5
|
9天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
9天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
18 2
|
12天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
23 0
|
1月前
|
数据采集 监控 安全
厂区地图导航制作:GIS技术与路径导航算法融合
在智能化、数字化时代,GIS技术为厂区的运营管理带来了革命性变化。本文探讨了如何利用GIS技术,通过数据采集、地图绘制、路径规划、位置定位和信息查询等功能,打造高效、精准的智能厂区地图导航系统,提升企业的竞争力和管理水平。
45 0
厂区地图导航制作:GIS技术与路径导航算法融合
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
18 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
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实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2