LeetCode-94. 二叉树的中序遍历

举报
小小谢先生 发表于 2022/04/15 22:32:22 2022/04/15
【摘要】 题目描述: 给定一个二叉树的根节点 root ,返回它的 中序 遍历。 输入:root = [1,null,2,3] 输出:[1,3,2] 思路分析: 用递归或是迭代算法来解决。 递归: 首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,...

题目描述:

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

输入:root = [1,null,2,3]
输出:[1,3,2]

思路分析:

用递归或是迭代算法来解决。

递归:

首先我们需要了解什么是二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义 inorder(root) 表示当前遍历到root 节点的答案,那么按照定义,我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树,然后将 root 节点的值加入答案,再递归调用inorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。


  
  1. class Solution {
  2. public List<Integer> inorderTraversal(TreeNode root) {
  3. List<Integer> res = new ArrayList<Integer>();
  4. inorder(root, res);
  5. return res;
  6. }
  7. public void inorder(TreeNode root, List<Integer> res) {
  8. if (root == null) {
  9. return;
  10. }
  11. inorder(root.left, res);
  12. res.add(root.val);
  13. inorder(root.right, res);
  14. }
  15. }

迭代法:

递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其他都相同,具体实现可以看下面的代码。


  
  1. class Solution {
  2. public List<Integer> inorderTraversal(TreeNode root) {
  3. List<Integer> res = new ArrayList<Integer>();
  4. Deque<TreeNode> stk = new LinkedList<TreeNode>();
  5. while (root != null || !stk.isEmpty()) {
  6. while (root != null) {
  7. stk.push(root);
  8. root = root.left;
  9. }
  10. root = stk.pop();
  11. res.add(root.val);
  12. root = root.right;
  13. }
  14. return res;
  15. }
  16. }

文章来源: blog.csdn.net,作者:小小谢先生,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/xiewenrui1996/article/details/113529570

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。