[LeetCode] Binary Tree Inorder Traversal - c++编程基础

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

问题描述：给定一个二叉树，按中序遍历顺序返回它的节点的值。

对于二叉树的非递归便利要借助数据结构栈。

代码如下：

class Solution {  
public:  
    vector inorderTraversal(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(root == NULL)  
            return vector




(0);  
        stack sta;  
        TreeNode *pnode = root;  
        vector vec;  
  
        while(pnode || !sta.empty()) {  
            while(pnode) {  
                sta.push(pnode);  
                pnode = pnode->left;  
            }  
            if(!sta.empty()) {  
                pnode = sta.top();  
                vec.push_back(pnode->val);  
                sta.pop();  
                pnode = pnode->right;  
            }  
        }  
        return vec;  
    }  
};