Binary Tree Inorder Traversal【94】

Datetime:2016-08-23 01:22:02          Topic: LeetCode           Share

94. Binary Tree Inorder Traversal

My Submissions

Total Accepted:  102260 Total Submissions:  268492 Difficulty:  Medium

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree  {1,#,2,3} ,

1
    \
     2
    /
   3

return [1,3,2] .

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means?  > read more on how binary tree is serialized on OJ.

Subscribe to see which companies asked this question

Hide Tags
Tree   Hash Table   Stack

第一种方法,烂大街朴素递归

/**
 * 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) {
         if(root){  
            inorderTraversal(root->left);  
            result.push_back(root->val);  
            inorderTraversal(root->right);  
        }  
        return result;  
    }  
private:  
    vector<int> result; 
};

第二种方法:烂大街中序式深度递归搜索

/**
 * 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:
    void dfs(TreeNode *root, vector<int> &result) {  
            if(NULL == root)  
                return;  
            dfs(root->left, result);  
            result.push_back(root->val);  
            dfs(root->right, result);  
        }  
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root, result);  
        return result; 
    }  
private:  
    vector<int> result; 
};




About List