LeetCode 二叉树的中序遍历

梦里梦外; 2022-05-15 05:59 218阅读 0赞

94.二叉树的中序遍历
数据结构我是学过的,但是我用Java代码还没实现过,于是在做这个题时我看了一个先序遍历的例子,下边总结一下
中序遍历规则是:先遍历左子树,然后遍历中子树,最后遍历右子树。
先序遍历的规则是:先遍历中子树,然后是左子树,最后是右子树。
后序遍历的规则是:先遍历左子树,然后是右子树,最后是中子树。
这里有个记忆的小技巧:就是无论是中序,先序,后序,都是左子树在右子树的左边;还有中序,先序,后序都是以中子树的位置决定的,中序,中子树在中间,先序,中子树在第一个,后序中子树在最后。you get 到了吗?
即使在代码中,也是这个规则,无非是顺序的变换。
给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

  1. public List<Integer> inorderTraversal(TreeNode root) {
  2. List<Integer> list = new ArrayList<>();
  3. preHeader(root,list);
  4. return list;
  5. }
  6. private static void preHeader(TreeNode root,List<Integer> list) {
  7. if (root == null) return;
  8. // 这个顺序是根据它是什么遍历的顺序
  9. preHeader(root.left,list);
  10. list.add(root.val);
  11. preHeader(root.right,list);
  12. }

这里写图片描述

发表评论

表情:
评论列表 (有 0 条评论,218人围观)

还没有评论,来说两句吧...

相关阅读

    相关 LeetCode

    94.二叉树的中序遍历 数据结构我是学过的,但是我用Java代码还没实现过,于是在做这个题时我看了一个先序遍历的例子,下边总结一下 中序遍历规则是:先遍历左子树,然后遍