leetcode之binary-tree-inorder-traversal(二叉樹中序周遊)
題目
Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLzMjM2ADO0MjMzIjNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
return[1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
題意
給定一個二叉樹,求其i中序周遊的輸出;
C++實作代碼
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//非遞歸版本,使用stack,先全部擷取所有左子樹節點,然後再逐級向上,求其右子樹
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
stack<TreeNode *> s;
vector<int> v;
if(root ==nullptr)
return v;
TreeNode *node = root;
while(node != nullptr || !s.empty()){
while(node){
s.push(node);
node = node->left;
}
if(!s.empty()){
node = s.top();
s.pop();
v.push_back(node->val);
node = node->right;
}
}
return v;
}
};
C++遞歸版本
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
inorder(root,v);
return v;
}
void inorder(TreeNode *root,vector<int> & v){
if(root ==nullptr)
return ;
if(root->left){
inorder(root->left,v);
}
v.push_back(root->val);
if(root->right){
inorder(root->right,v);
}
}
};