給定一個二叉樹，返回它的中序?遍歷。

示例:

輸入: [1,null,2,3]1\2/3輸出: [1,3,2]

進階:?遞歸算法很簡單，你可以通過迭代算法完成嗎？

思路1：遞歸方法

?

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:vector<int> result;vector<int> inorderTraversal(TreeNode* root) {core(root);return result;}void core(TreeNode* root){if(root==NULL){return;}core(root->left);result.push_back(root->val);core(root->right);} };

思路2：非遞歸方法，利用棧解決?

?

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> result;TreeNode * pNode = root;while(pNode != NULL || !s.empty()){if(pNode != NULL){s.push(pNode); //當前結點入棧pNode = pNode->left; //轉向左子樹}else{ pNode = s.top(); result.push_back(pNode->val); //讀取棧頂數據s.pop(); //棧頂彈出pNode = pNode->right; //轉向右子樹}}return result;} };

?

總結

以上是生活随笔為你收集整理的二叉树的中序遍历—leetcode94的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。