給定一個二叉樹，回傳它的中序 遍歷，
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
進階: 遞回演算法很簡單，你可以通過迭代演算法完成嗎？
解題思路：
這是最簡單的中序遍歷題目，如果用遞回即dfs的方法，幾步就可以完成，思路很容易理解，代碼如下：
/**
* 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;
if(!root){
return ans;
}
dfs(ans, root);
return ans;
}
void dfs(vector<int>& ans, TreeNode* root){
if(root->left){
dfs(ans, root->left);
}
ans.push_back(root->val);
if(root->right){
dfs(ans, root->right);
}
}
};
當然也可以用迭代的演算法，這里使用的資料結構是堆疊的方式，思路是不停地把左子節點放入堆疊中，直到沒有，這時候出堆疊，然后再往右子節點走，代碼如下：
/**
* 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*> st;
TreeNode* cur = root;
while(!st.empty() || cur != NULL){//指標不為慷訓堆疊不為空
if(cur != NULL){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();
st.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/50897.html
標籤：其他