题解 | #二叉树的中序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstddef>
#include <stack>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */

    vector<int> inorderTraversal(TreeNode* root) {
        // write code here

        stack<TreeNode*>tree;
        vector<int> v;
        while (root || !tree.empty()) {
            while (root) {
                tree.push(root);
                root = root->left;
            }
            root = tree.top();
            v.push_back(root->val);
            tree.pop();
            root = root->right;

        }
        return v;
    }
};

非递归方法

栈和vector容器，中序遍历，左根右。需要从根左支的最左节点开始存。

        while (root) {
            tree.push(root);
            root = root->left;
        }

从根节点一路往左，进栈。一直到最左节点。最左节点先存。 root = tree.top() ; v.push_back(root->val); 然后出栈这个栈顶元素。 tree.pop(); 出栈之后的栈顶元素就是最左节点的父节点， 此时root是指向最左节点的，栈顶是最左节点的父节点，root = root->right;就是将root指向最左节点的右孩子节点。如果存在右孩子节点，那么root指向右孩子节点，进行下一层循环。也就是继续判断右孩子节点是否有左孩子，有的话就入栈往左支转。如果不存在右孩子节点，root当前指向空，那么下一层循环时，while (root) 这里面就不会进行。把当前栈顶出栈，存。按这样的逻辑进行下去。