[LeetCode]Binary Tree Inorder Traversal-白红宇

[LeetCode]Binary Tree Inorder Traversal

阅读量：4150 次

发布时间：2019-05-25

本文共 1992 字，大约阅读时间需要 6 分钟。

struct TreeNode {	int val;	TreeNode *left;	TreeNode *right;	TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {//recursive to iterative, we always need stack//thought of the stack of recursive function, then we can come//up with the iterative version easily. //turn recursive into iterative//if(root), s.push(root)(save the scene, just like function stack), root=root->left(get to the next level, called by function itself)//if(!root), set root=s.top()(get the nearest scene) visit its value and then set root=root->right(get to the next level, called by function itself)public:	vector
   
     inorderTraversal(TreeNode *root) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		vector
    
      res;		stack
     
       s;		TreeNode* current = root;		while (true)		{			//add all left in			if(current)			{				s.push(current);				current = current->left;			}			else			{				if(s.empty())					break;				current = s.top();				s.pop();				res.push_back(current->val);				current = current->right;			}		}		return res;	}};

second time

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
   
     inorderTraversal(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        stack
    
      nodeS;        TreeNode* cur = root;        vector
     
       ans;        while(true)        {            if(cur != NULL)            {                nodeS.push(cur);                cur = cur->left;                }            else            {                if(!nodeS.empty())                {                    ans.push_back(nodeS.top()->val);                    cur = nodeS.top()->right;                    nodeS.pop();                }                else break;//terminate case            }        }        return ans;    }};