leetcode:Binary Tree Inorder Traversal

leetcode:Binary Tree Inorder Traversal

一、 題目

給一個二叉樹，中序遍歷這個樹，輸出得到的值

二、 分析

這道題前面見到了，多次隔過去了，今天終於面對了，當時是沒有好的思路，自習想想越是太難，Leetcode上的題，遞歸是統法啊！

方法一：遞歸

1. 開辟數組，遞歸左節點

2. 將中間結點放入數組

3. 遞歸有節點

方法二：使用數組和棧

1. 將根節點入棧

2. 設置標志或判斷條件，一直向左入棧

3. 出棧並入數組

基本上遞歸和非遞歸思路就是這樣，很簡單的說。

/**
 * 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) {
        vector ans;
		inorder(root,ans);
		return ans; 
    }
    
    void inorder(TreeNode *node,vector&ans)
    {
    	if(node == NULL)
    		return;
    	inorder(node->left,ans);
    	ans.push_back(node->val);
    	inorder(node->right,ans);
    }
};

/**
 * 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) {
        vector ans;
        stack sta;
        TreeNode *ptr = root;
        while(!sta.empty()||ptr){
        	if(ptr){
        		sta.push(ptr);
        		ptr = ptr->left;
        	}
        	else {
        		ptr = sta.top();
        		sta.pop();
        		ans.push_back(ptr->val);
        		ptr = ptr->right;
        	}
        }
		return ans; 
    }
};

/**
 * 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) {
        vector ans;
        if(!root)
        	return ans;
        stack sta;
        sta.push(root);
        while(!sta.empty()){
        	while(sta.top()->left)
        		sta.push(sta.top()->left);
            TreeNode *t = sta.top();
            ans.push_back(t->val);
            sta.pop();
            if(!sta.empty())
            	sta.top()->left = NULL;
            if(t->right) 
            	sta.push(t->right);
		}
		return ans; 
    }
};