網址：https://leetcode.com/problems/binary-tree-inorder-traversal/

參考：https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

二叉樹的遍歷一般有兩種辦法：遞歸、通過棧進行迭代。此外，還有通過模擬線索二叉樹進行遍歷的方式。

遞歸的代碼十分簡單，這里就不再贅述。

中序遍歷迭代遍歷算法：

• 遇到一個節點，就把它圧棧，并去遍歷它的左子樹
• 當左子樹遍歷結束后，從棧頂彈出這個節點并訪問它
• 然后再去中序遍歷它的右子樹

/*** 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) {vector<int> ans;stack<TreeNode*> temp;while( root || !temp.empty()){while(root){temp.push(root);root = root->left;}if(!temp.empty()){root = temp.top();temp.pop();ans.push_back(root->val);root = root->right;}}return ans;} };

“線索”二叉樹：

在這里我們不必為節點添加額外的指針域來表示節點的某種遍歷順序的前后位置分別是什么節點，

而是通過以線索二叉樹的思想遍歷二叉樹，把樹直接改造成可直接向下遍歷的結構。

具體可見：https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

/*** 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) {vector<int> ans;TreeNode* temp = new TreeNode(0);// 因為我們不斷讓root=root->right，所以判斷條件為root != NULLwhile(root != NULL){// root有左子樹，就把root修改為左子樹的最右節點的右節點if(root->left){// 得到root左子樹的最右節點temp = root->left;while(temp->right != NULL){temp = temp->right;}// 把root修改為左子樹的最右節點的右節點temp->right = root;// 注意要把root節點的左節點置為NULL！// 在這之前先存下root的左節點，然后修改root，進行下一輪while循環temp = root->left;root->left = NULL;root = temp;}else{// root沒有左子樹，說明當前節點是當前樹中的最左節點// 根據中序遍歷的定義，把val存入ans，繼續while循環ans.push_back(root->val);root = root->right;}}return ans;} };

?

轉載于:https://www.cnblogs.com/tornado549/p/10799742.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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