LeetCode 中级 - 中序遍历二叉树
程序员文章站
2022-05-19 21:05:40
...
中序遍历二叉树
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
分析
只需要记住中序遍历的顺序:左->中->右
代码
只实现递归版本
迭代可以考虑使用栈存储遍历过的节点,“返回上一层”时,栈顶节点出栈
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//中序的顺序:左->根->右
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> lists = new LinkedList<>();
if(root == null){
return lists;
}
else inOrder(lists,root);
return lists;
}
private void inOrder(List<Integer> list,TreeNode root){
if(root == null){
return;
}else{
inOrder(list,root.left);
list.add(root.val);
inOrder(list,root.right);
}
}
}