画解算法:94. 二叉树的中序遍历
2019-07-31 本文已影响47人
DeppWang
题目链接
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
题目描述
给定一个二叉树,返回它的中序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
解题方案
思路1:使用递归
- 中序遍历也叫中根遍历,遍历时,根节点顺序在中间,即左跟右。先根遍历:根左右;后根遍历:左右根。
- 中根遍历最重要的一点是:如果当前节点没有左子树,记录其值。
- 成功使用递归的关键:保证每一个节点的值都会被记录,递归有两个条件:递归条件和基线条件。
- 递归条件:用于函数自己调用自己。这里设置为如果左/右子树不为空,递归调用。
- 基线条件:用于保证递归会结束。这里不用设置,因为只要树不是无穷的,递归就能结束。
- 在计算机内部,使用调用栈(Call Stack)来存放函数。调用另一个函数时,当前函数暂停并处于为完成状态,该函数的所有变量的值都还在内存中。
- 时间复杂度:O(n)。
代码
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
traversal(root, list);
return list;
}
private void traversal(TreeNode root, List<Integer> list) {
if (root != null) {
if (root.left != null) {
traversal(root.left, list);
}
list.add(root.val);//如果当前节点没有左子树,记录其值
if (root.right != null) {
traversal(root.right, list);
}
}
}
}
画解


















思路2:使用栈
- 使用递归时,如果没有结合到函数调用栈理解的话,不太好理解
- 在计算机内部,使用调用栈来存放函数,所以可以直接使用栈来实现,更形象
- 具体参考LeetCode官方题解方法二