LeetCode OJ——Binary Tree Inorder Traversal

http://oj.leetcode.com/problems/binary-tree-inorder-traversal/

树的中序遍历，递归方法，和非递归方法。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void subfunction(TreeNode *root,vector<int> &result)
    {
        if(root == NULL)
            return;
        subfunction(root->left,result);
        result.push_back(root->val);
        subfunction(root->right,result);
    }
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
     vector<int> result;
     result.clear();
     subfunction(root,result);
     return result;
     
    }
};

 1 #include <iostream>;
 2 #include<stack>
 3 #include<vector>
 4 using namespace std;
 5 
 6  //Definition for binary tree
 7   struct TreeNode {
 8       int val;
 9       TreeNode *left;
10       TreeNode *right;
11       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12  };
13   class Solution {
14 
15       
16   private:
17       void instack(TreeNode * root,stack< TreeNode*> &datastack )
18       {
19           if(root ==NULL)
20               return;
21           while(root ->left!=NULL)
22           {
23               datastack.push(root ->left);
24               root = root ->left;
25           }
26       }
27   public:
28       vector< int> inorderTraversal(TreeNode *root) {
29           // Note: The Solution object is instantiated only once and is reused by each test case.
30           stack<TreeNode *> datastack;
31           
32           vector<int> result;
33           result.clear();
34           if(root==NULL)
35               return result;
36           datastack.push(root);
37           instack( root,datastack);
38           
39           TreeNode* tempNode = (TreeNode*)malloc(sizeof(TreeNode));
40           while(datastack.empty()==false)
41           {
42               tempNode = datastack.top();
43               result.push_back(tempNode->val);
44               datastack.pop();
45               if(tempNode->right==NULL )
46                   continue;
47               else
48               {
49                   datastack.push(tempNode->right);
50                   instack(tempNode->right,datastack);
51               }
52           }
53           return result;
54       }
55   };

#include<iostream>
#include"cla.h"
using namespace std;

int main()
{
    TreeNode *myroot = (TreeNode*)malloc(sizeof(TreeNode));
    myroot->val = 0;
    
    TreeNode *myroot2 = (TreeNode*)malloc(sizeof(TreeNode));
    myroot2->val = -3;
    myroot2->left = NULL;
    myroot2->right = NULL;

    TreeNode *myroot3 = (TreeNode*)malloc(sizeof(TreeNode));
    myroot3->val = 5;
    myroot3->left = NULL;
    myroot3->right = NULL;

    myroot->left = myroot2;
    myroot->right = myroot3;

    TreeNode *myroot4 = (TreeNode*)malloc(sizeof(TreeNode));
    /*myroot4->val = 9;*/
    /*myroot3->right =myroot4;*/
    myroot4->left = NULL;
    myroot4->right = NULL;


    Solution *pSolution = new Solution;
    
    vector<int> result;
    result = pSolution->inorderTraversal(NULL);
    for(int i = 0;i<result.size();i++)
        cout<<result[i]<<"   ";

    if(pSolution!=NULL)
        delete pSolution;
    pSolution = NULL;

    return 0;
}