C/C++ BM24二叉树的中序遍历

前言

中序遍历和前序遍历的不同地方简单改过就是根的位置不同罢了。
具体参考C/C++ BM23 二叉树的前序遍历

---

题目

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 $0\le n\le 1000$，树上每个节点的值满足 $-1000\le val\le 1000$
进阶：空间复杂度 $O(n)$，时间复杂度 $O(n)$

输入： { 1 , 2 , # , # , 3 } \{1,2,\#,\#,3\} {1,2,#,#,3}
返回值：$[2,3,1]$

说明：

示例2
输入： {}
返回值$[]$

输入：$1,2$
返回值：$[2,1]$
说明：

输入： { 1 , # , 2 } \{1,\#,2\} {1,#,2}
返回值：$[1,2]$

说明：

备注
树中节点数目在范围 $[0,100]$ 内
树中的节点的值在$[-100,100]$以内

解决方案一

1.1 思路阐述

中序遍历是是什么：

一棵树有根节点，根节点下面有左子树和右子树。左子树和右子树的根节点为这棵树根节点的左节点和右节点。

中序遍历的意思就是，左根右。先遍历左子树再遍历根节点，最后再遍历右子树。

1.2 源码

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> temp;
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) //如果节点为空，则返回原数组
            return temp;
        inorderTraversal(root->left);//遍历当前子树的左节点
        temp.push_back(root->val);//不为空则表示遍历到这个节点，将这个节点的值添加到数组中
        inorderTraversal(root->right);//遍历当前子树的右节点

        return temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解决方案二

这个我就不贴了，都一样的。顶多就是把函数功能单独拎出来。

总结

明白了前序遍历，这个中序遍历无非就是换个顺序的问题。