二叉数的中序遍历原理及例题Leetcode（94. 二叉树的中序遍历 c++实现）

1.中序遍历

中序遍历的步骤为 :   遍历左孩子-->  遍历根节点--> 遍历右孩子

如上图，这颗树由5个节点，A，B，C，D，E组成。其中a为根节点 ，b为左子树，cde为右子树

遍历顺序为 A （根节点）   ---->    B(左子树)   --->    (右子树)

其中右子树又包含三个节点cde，在右子树中，c为根节点，d为左子树，e为右子树

遍历顺序为 C （根节点）   ---->    D(左子树)   --->    E(右子树)

所以总的遍历顺序为A ->B->C->D->E

2.中序遍历的实现

知道了原理，实现就很简单了。

我们可以定义一个函数 midorder()

midorder(根节点的地址)
{
 if  （根节点空）退出；
 if （左子树非空):
      midorder(左子树的地址)；
      遍历根节点；
 if （右子树非空):
      midorder(右子树的地址)；
}

=========代码实现如下=====

void midorder(TreeNode *root)
    {
       if (!root) ;
       if (root ->left)  midorder(root -> left) ;
       if (root ->right)  midorder(root -> right) ;
    }

3.例题Leetcode（94. 二叉树的中序遍历 c++实现）

如上图注释所示，树的数据结构为：

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
}

将树中序遍历的代码如下：

class Solution {

   public:
               vector<int> inorderTraversal(TreeNode* root) {    
               midorder(root)        
                 }    

    void midorder(TreeNode *root)
    {
       if (!root)  return ;
       if (root ->left)  midorder(root -> left) ;
       if (root ->right)  midorder(root -> right) ;
    }
}；

此代码只是把树中序遍历一遍，现在，我们要把遍历的东西保存在数组中，源码如下。

class Solution {

 

   public:

               vector<int> inorderTraversal(TreeNode* root) {    

               vector<int> resultarray;  // 定义需要返回的结果数组

               midorder(root,resultarray);

               return resultarray;    

                 }  

    void midorder(TreeNode *root,vector<int> &res)   // 多定义一个需要返回的函数

    {

       if (!root)  return ;

       if (root ->left)  midorder(root -> left,res);

       res.push_back(root->val);    // push_back函数：在数组末尾追加东西

       if (root ->right)  midorder(root -> right,res);

    }

};