LeetCode 二叉树的中序遍历
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);
}
还没有评论,来说两句吧...