代码随想录 待我称王封你为后i 2024-02-22 09:16 44阅读 0赞 ## 前言 ## 代码随想录算法训练营day14 -------------------- ## 一、Leetcode \#\#\#\# 144. 二叉树的前序遍历 ## ### 1.题目 ### 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 示例 1: 输入:root = \[1,null,2,3\] 输出:\[1,2,3\] 示例 2: 输入:root = \[\] 输出:\[\] 示例 3: 输入:root = \[1\] 输出:\[1\] 示例 4: 输入:root = \[1,2\] 输出:\[1,2\] 示例 5: 输入:root = \[1,null,2\] 输出:\[1,2\] 提示: css 复制代码 `树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/bi…][leetcode.cn_problems_bi] ### 2.解题思路 ### 方法一:递归 首先我们需要了解什么是二叉树的前序遍历:按照访问根节点——左子树——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。 定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要首先将 root 节点的值加入答案,然后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。 ### 3.代码实现 ### java 复制代码 `class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); preorder(root, res); return res; } public void preorder(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); preorder(root.left, res); preorder(root.right, res); } }` ## 二、Leetcode 145. 二叉树的后序遍历 ## ### 1.题目 ### 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 输入:root = \[1,null,2,3\] 输出:\[3,2,1\] 示例 2: 输入:root = \[\] 输出:\[\] 示例 3: 输入:root = \[1\] 输出:\[1\] 提示: css 复制代码 `树中节点的数目在范围 [0, 100] 内 -100 <= Node.val <= 100` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/bi…][leetcode.cn_problems_bi 1] ### 2.解题思路 ### 方法一:递归 首先我们需要了解什么是二叉树的后序遍历:按照访问左子树——右子树——根节点的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。 定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树,然后递归调用 postorder(root->right) 来遍历 root 节点的右子树,最后将 root 节点的值加入答案即可,递归终止的条件为碰到空节点。 ### 3.代码实现 ### java 复制代码 `class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); postorder(root, res); return res; } public void postorder(TreeNode root, List<Integer> res) { if (root == null) { return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); } }` ## 三、Leetcode 94. 二叉树的中序遍历 ## ### 1.题目 ### 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 示例 1: 输入:root = \[1,null,2,3\] 输出:\[1,3,2\] 示例 2: 输入:root = \[\] 输出:\[\] 示例 3: 输入:root = \[1\] 输出:\[1\] 提示: css 复制代码 `树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/bi…][leetcode.cn_problems_bi 2] ### 2.解题思路 ### 方法一:递归 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。 定义 inorder(root) 表示当前遍历到 rootroot 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 rootroot 节点的左子树,然后将 rootroot 节点的值加入答案,再递归调用inorder(root.right) 来遍历 rootroot 节点的右子树即可,递归终止的条件为碰到空节点。 ### 3.代码实现 ### java 复制代码 `class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } public void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); } }` [leetcode.cn_problems_bi]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbinary-tree-preorder-traversal [leetcode.cn_problems_bi 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbinary-tree-postorder-traversal [leetcode.cn_problems_bi 2]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbinary-tree-inorder-traversal
相关 代码随想录 前言 代码随想录算法训练营day44 -------------------- 一、Leetcode 518. 零钱兑换 II 1.题目 给你一个整数数组 布满荆棘的人生/ 2024年02月22日 09:45/ 0 赞/ 54 阅读
相关 代码随想录 前言 代码随想录算法训练营day14 -------------------- 一、Leetcode \\\\ 144. 二叉树的前序遍历 1.题目 给你 待我称王封你为后i/ 2024年02月22日 09:16/ 0 赞/ 45 阅读
相关 代码随想录 一、Leetcode 20. 有效的括号 1.题目 给定一个只包括 '(',')','\{','\}','\[','\]' 的字符串 s ,判断字符串是否有效。 ﹏ヽ暗。殇╰゛Y/ 2024年02月22日 09:15/ 0 赞/ 62 阅读
相关 代码随想录 前言 代码随想录算法训练营day06 -------------------- 一、哈希表基础知识 【 [代码随想录][Link 1]】 【[菜鸟教 桃扇骨/ 2024年02月22日 09:14/ 0 赞/ 48 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 女爷i/ 2024年02月22日 04:39/ 0 赞/ 82 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 朱雀/ 2024年02月22日 04:38/ 0 赞/ 109 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 叁歲伎倆/ 2024年02月22日 04:37/ 0 赞/ 63 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 左手的ㄟ右手/ 2024年02月22日 02:29/ 0 赞/ 52 阅读
相关 代码随想录 前言 代码随想录算法训练营day35 -------------------- 一、Leetcode 860.柠檬水找零 1.题目 在柠檬水摊上,每一杯柠 朱雀/ 2024年02月22日 02:26/ 0 赞/ 116 阅读
相关 代码随想录 前言 代码随想录算法训练营day34 -------------------- 一、Leetcode 1005.K次取反后最大化的数组和 1.题目 给你一 ゞ 浴缸里的玫瑰/ 2024年02月22日 02:25/ 0 赞/ 40 阅读
还没有评论,来说两句吧...