二叉树——94 二叉树的中序遍历(medium)

 1 /*
 2  * @lc app=leetcode.cn id=94 lang=cpp
 3  *
 4  * [94] 二叉树的中序遍历
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
15  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
16  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17  * };
18  */
19 class Solution {
20 public:
21     // //迭代方法，需要显式地将这个栈模拟出来
22     // vector<int> inorderTraversal(TreeNode* root) {
23     //     vector<int> result;
24     //     stack<TreeNode*> st;
25     //     while(root!=nullptr||!st.empty()){
26     //         while(root!=nullptr){
27     //              st.push(root);
28     //              root=root->left;
29     //         }           
30     //         root=st.top();
31     //         st.pop();
32     //         result.push_back(root->val);
33     //         root=root->right;
34             
35     //     }        
36     //     return result;
37     //}
38 
39 
40     //递归方法
41     vector<int> inorderTraversal(TreeNode* root){
42         if(root==nullptr) return {} ;  //vector 返回空值
43         vector<int> res;
44         inorder(root,res);
45         return res;
46     }
47 
48     void inorder(TreeNode* root,vector<int>& res){
49         if(root==nullptr) return;
50         inorder(root->left,res);/*一直递归左子树直至到达叶子节点*/
51         res.push_back(root->val);/*左子树为空时，开始打印根节点*/
52         inorder(root->right,res);/*开始递归根节点的右子树*/
53     }
54 };
55 // @lc code=end