Leetcode Binary Tree Inorder Traversal

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

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

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

confused what "{1,#,2,3}" means?

递归解决方案

class Solution {

public:

    vector<int> res;

    void inorder(TreeNode* root){

        if(root == NULL) return;

        inorder(root->left);

        res.push_back(root->val);

        inorder(root->right);

    }

    vector<int> inorderTraversal(TreeNode *root) {

        inorder(root);

        return res;

    }

};

递归中序遍历

非递归解决方案

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> res;

        if(root == NULL) return res;

        stack<TreeNode *> nodeStack;

        TreeNode *current = root;

        while(!nodeStack.empty() || current ){

            if(current != NULL){

                nodeStack.push(current);

                current = current->left;

            }else{

                current = nodeStack.top();nodeStack.pop();

                res.push_back(current->val);

                current = current->right;

            }

        }

        return res;

    }

};

非递归中序遍历

巴特西

Leetcode Binary Tree Inorder Traversal

最新文章

热门文章