LeetCode 二叉树的中序遍历-蒲公英云

LeetCode 二叉树的中序遍历

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

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

示例:

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

2
/
3

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

public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>();
       preHeader(root,list);
       return list;
    }
    private static void preHeader(TreeNode root,List<Integer> list) {
        if (root == null) return;
        // 这个顺序是根据它是什么遍历的顺序
        preHeader(root.left,list);
        list.add(root.val);
        preHeader(root.right,list);
    }