LeetCode 94. Binary Tree Inorder Traversal 二叉树的中序遍历 C++

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

Example:

Input: [,null,,]

    \

    /

Output: [,,]

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

题目中要求使用迭代用法，利用栈的“先进后出”特性来实现中序遍历。

解法一：（迭代）将根节点压入栈，当其左子树存在时，一直将其左子树压入栈，直至左子树为空，将栈顶元素弹出，将其val值放入vector中，再将其右子树循环上述步骤，直到栈为空。

（C++）

 vector<int> inorderTraversal(TreeNode* root) {

         vector<int> m={};

         stack<TreeNode*> stack;

         if(!root)

             return m;

         TreeNode* cur=root;

         while(!stack.empty()||cur){

             while(cur){

                 stack.push(cur);

                 cur=cur->left;

             }

             cur=stack.top();

             m.push_back(cur->val);

             stack.pop();

             cur=cur->right;

         }

         return m;

     }

方法二：使用递归（C++）

 void inorder(vector<int> &m,TreeNode* root){

         if(root==NULL)

             return;

         inorder(m,root->left);

         m.push_back(root->val);

         inorder(m,root->right);

     }

     vector<int> inorderTraversal(TreeNode* root) {

         vector<int> m={};

         if(root==NULL)

             return m;

         inorder(m,root);

         return m;

     }

巴特西

LeetCode 94. Binary Tree Inorder Traversal 二叉树的中序遍历 C++

最新文章

热门文章