leetcode,編程題,二叉樹,中序遍歷,非遞歸實現,迭代實現 ...
- 題目描述 (原題目鏈接)
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3]
,
1 \ 2 / 3
return [1,3,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) { vector<int> results; if(root == NULL) return results; stack<TreeNode*> nodes; nodes.push(root); TreeNode* curr; int shouldFindLeft = 1; while(!nodes.empty()) { curr = nodes.top(); // add all left nodes if(shouldFindLeft == 1) { while(curr->left != NULL) { nodes.push(curr->left); curr = curr -> left; } } // print curr node results.push_back(curr->val); nodes.pop(); // add its right child if(curr->right != NULL) { nodes.push(curr->right); shouldFindLeft = 1; } else { shouldFindLeft = 0; } } return results; } };