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; } };