[Leetcode] Binary Tree Inorder Traversal

Binary Tree Inorder Traversal 题解

原创文章，拒绝转载

题目来源：https://leetcode.com/problems/binary-tree-inorder-traversal/description/

---

Description

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

Example

Given binary tree [1,null,2,3],

   1
    
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution

class Solution {
private:
    void inOrder(TreeNode* node, vector<int>& res) {
        if (node != NULL) {
            inOrder(node -> left, res);
            res.push_back(node -> val);
            inOrder(node -> right, res);
        }
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inOrder(root, res);
        return res;
    }
};

---

解题描述

这道题是经典的二叉树中序遍历问题。上面给出来的是递归的做法。迭代的做法基本想法还是使用栈来模拟递归调用：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == NULL)
            return res;
        stack<TreeNode*> nodeStack;

        TreeNode *curNode = root;

        while (curNode != NULL || !nodeStack.empty()) {  // 只有当前节点为空且栈为空的时候遍历才结束
            while (curNode != NULL) {  // 一直探测到左侧分支的尽头
                nodeStack.push(curNode);
                curNode = curNode -> left;
            }
            curNode = nodeStack.top();
            nodeStack.pop();
            res.push_back(curNode -> val);  // 访问当前节点，即父节点（左侧已经为空）
            curNode = curNode -> right;  // 当前节点设置为右子节点
        }


        return res;
    }
};