LeetCode刷题笔记（Binary Tree Inorder Traversal）

接下来又刷了一道类似的题目，思想和前面那道前序遍历差不多，下面就来分享一下经验。

题目如下：

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

题意分析： 

给定一个二分搜索树，返回中序遍历后节点的值。如果不使用递归方法，用其他的方法呢？

解答如下：

方法一（递归法）

和“https://blog.****.net/Vensmallzeng/article/details/88907167”的方法一思想一样，只是将res.push_back( node -> val ); 操作的位置换一下。

class Solution{
public:
    vector<int> inorderTraversal( TreeNode* node ){
        vector<int> res;
        if( !node )
            return res;
        recursive(node, res);
        return res;
    }

    void recursive( TreeNode* node, vector<int>& res ){
        if( node )
        {            
            recursive( node -> left, res);
            res.push_back( node -> val );       ////此处操作便为中序遍历
            recursive( node -> right, res);
        }
    }
};

提交后的结果如下：

 

 

方法二（非递归法）

和“https://blog.****.net/Vensmallzeng/article/details/88907167”的方法二思想一样，只是将stack.push( Instruction( "Out", instruction.node ) ); 操作的位置换一下。

struct Instruction{
    string s;
    TreeNode* node;
    Instruction(string s, TreeNode* node): s(s), node(node){}
};

class Solution{
public:
    vector<int> inorderTraversal( TreeNode* node ){

        vector<int> res;
        if ( !node ) return res;

        stack<Instruction> stack;
        stack.push( Instruction("Go", node) );
        while ( !stack.empty() ){

            Instruction instruction = stack.top();
            stack.pop();

            if ( instruction.s == "Out" ) res.push_back( instruction.node->val );
            else{
                assert( instruction.s == "Go" );
                if ( instruction.node -> right )
                    stack.push( Instruction( "Go", instruction.node->right ));
                stack.push( Instruction( "Out", instruction.node ) );  // 此处操作便为中序遍历
                if ( instruction.node -> left )
                    stack.push( Instruction( "Go", instruction.node->left ));
            }
        }
     return res;
    }
};

提交后的结果如下：

 

日积月累，与君共进，增增小结，未完待续。