廊坊做网站公司排名专业网站推广优化

题目来源

力扣每日一题；题序：94

我的题解

方法一 递归方式

使用递归实现，结果List也可以定义为一个类变量。
按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，可以直接用递归函数来模拟这一过程。

时间复杂度：O(n)
空间复杂度：O(n)

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();inOrder(root,res);return res;
}
public void inOrder(TreeNode root,List<Integer> res){if(root==null){return ;}inOrder(root.left,res);res.add(root.val);inOrder(root.right,res);
}

方法二 非递归方式

使用栈来实现中序遍历的非递归方式。先一直往左遍历，并使用栈记录经过的节点，然后出栈将当前节点加入遍历结果中，再看当前节点是否有右子树节点。

时间复杂度：O(n)
空间复杂度：O(n)

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();if(root==null)return res;LinkedList<TreeNode> stack=new LinkedList<>();TreeNode t=root;//没有遍历完或者栈是空的while(t!=null||!stack.isEmpty()){//先一路向左while(t!=null){stack.push(t);t=t.left;}//到最左，开始出栈TreeNode temp=stack.pop();res.add(temp.val);//再看右边t=temp.right;}return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~