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 的执行结果：