LeetCode 94二叉木の中序はHERODINGのLeetCodeの道を遍歴する
二叉木を指定し、その中序遍歴を返します.
例:
入力:[1,null,2,3]12/3
出力:[1,3,2]
ステップアップ:再帰アルゴリズムは簡単ですが、反復アルゴリズムでできますか?
解題構想:これは最も簡単な中序遍歴問題であり、再帰的なdfsの方法であれば、数歩で完成することができ、構想は理解しやすく、コードは以下の通りである.
もちろん反復アルゴリズムも使用できますが、ここで使用するデータ構造はスタックの方式で、左サブノードをスタックに入れ続け、ないまでスタックを出て、右サブノードに行きます.コードは以下の通りです.
例:
入力:[1,null,2,3]12/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;
}
};