94.二叉树中序

题目描述

给定一个二叉树，返回它的中序 遍历。
输入: [1,null,2,3]
1

2
/
3

输出: [1,3,2]

问题分析

二叉树中序遍历的特点为先左，再根，最后右节点的顺序进行遍历。因为主要可分为两种方法

• 递归遍历
• 利用栈性质进行遍历 （双百）

解题思路1

• 递归遍历

class Solution {
 public:

     //vector<int> ans;
     void helper(TreeNode* root, vector<int> &ans)
     {
         if (root->left != nullptr)
         {
             helper(root->left, ans);
         }
         ans.push_back(root->val);
         if (root->right != nullptr)
         {
             helper(root->right, ans);
         }
         //return ans;

     }
     vector<int> inorderTraversal(TreeNode* root) {
         vector<int> ans;
         //注意判断条件
         TreeNode* head = root;
         if (head == nullptr)
         {
             return ans;
         }
         helper(head, ans);
         return ans;
     }
 };

解题思路2

利用栈后进先出的存储结构方式进行遍历

/**
 * 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 {
 public:

     vector<int> inorderTraversal(TreeNode* root) {
         vector<int> ans;
         //注意判断条件
         TreeNode* head = root;
         stack <TreeNode*> S;

         while (head || S.size())
         {
             //遍历到最左子树，依次放入栈中
             while (head)
             {
                 S.push(head);
                 head = head->left;
             }
             head = S.top();
             S.pop();
             ans.push_back(head->val);
             head = head->right;
         }  
         return ans;
     }
 };