LeetCode | 94.二叉树的中序遍历
这次来写一下 LeetCode 的第 94 题，二叉树的中序遍历。
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
这是一道关于二叉树的题，中序遍历是二叉树按照遍历节点的顺序进行遍历的一种方式。题目中给出了二叉树的一个定义，以及要完成遍历方法的定义。本题目我使用 Java 和 C++ 两种语言进行了实现，分别来看看 Java 和 C++ 对于二叉树给出的定义，以及题目给出的需要完成的代码。
C++ 的定义如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
}
};Java 的定义如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
}
}题目分析
二叉树，顾名思义就是一个节点最多只有两个分叉，如果出现三个分叉就不是二叉树了。二叉树根据节点的遍历顺序，一般分为 前序遍历、中序遍历、后序遍历以及层次遍历。如果按照遍历方式进行遍历，一般分为 递归遍历 和 迭代遍历（非递归遍历）。
我这里采用递归遍历的方式，递归遍历的好处是思路清晰，代码简洁，而它的缺点是性能比较低。当然了，递归的性能低主要看递归的深度，或者说规模，如果只是简单的递归也还行。除此而外，递归会大量的使用栈空间，如果递归深度过深的话，肯定会导致栈“爆”掉。
什么是中序遍历？二叉树的中序遍历，是输出左子树，再输出根节点，最后再输出右子树。比如题目中给出的遍历输出的顺序是 1、3、2 这样。为什么呢？
1 是根节点，而它没有做子树，因此就直接输出了根节点。而 1 的右子树，是以 2 为根节点的，2 有左子树，2 的左子树是 3，因此先输出 3，再输出 2，由于 2 没有右子树，因此遍历完成。
再来看一个例子，如下图：
上面的图，同样是按照中序遍历的话，遍历的结果是 2、3、4、5、6、7、8 这样的顺序。二叉树的遍历还是很容易理解的。
代码实现
先来看看 Java 的代码实现，
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> list = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
if (root.left != null) {
inorderTraversal(root.left);
}
list.add(root.val);
if (root.right != null) {
inorderTraversal(root.right);
}
return list;
}
}再来看看 C++ 的代码实现：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<int> node;
public:
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return node;
}
if (root->left != nullptr) {
inorderTraversal(root->left);
}
node.push_back(root->val);
if (root->right != nullptr) {
inorderTraversal(root->right);
}
return node;
}
};无论是从 C++ 的代码，还是从 Java 的代码都可以看出，通过递归的方式遍历二叉树真的是十分的简单。
提交结果
在写完 inorderTraversal 函数体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。
C++ 的执行结果：
Java 的执行结果：
