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},
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);
}
}
};