94 二叉树的中序遍历
程序员文章站
2022-03-03 11:03:59
...
题目描述:
给定一个二叉树,返回它的中序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
方法1:递归
主要思路:
(1)正常的使用中序遍历即可;
/**
* 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:
//中序遍历
void inorder(TreeNode* root,vector<int>& res){
if(root==NULL)//正常的终止条件
return ;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
//处理特殊的情形
if(root==NULL)
return vector<int>();
vector<int> res;
inorder(root,res);
return res;
}
};
方法2:使用栈实现迭代代码1
主要思路:
(1)使用栈实现,具体细节如代码所示;
/**
* 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) {
//处理特殊的情形
if(root==NULL)
return vector<int>();
stack<TreeNode*>st;
st.push(root);//压入根节点
TreeNode* tmp=NULL;
vector<int> res;
//栈非空,既未遍历完
while(!st.empty()){
//将左结点压入到栈中
while(st.top()->left)
st.push(st.top()->left);
//将结点弹出
while(true){
tmp=st.top();
st.pop();
res.push_back(tmp->val);
if(tmp->right){//若右结点非空,则压入右结点,然后跳出弹出循环
st.push(tmp->right);
break;
}
if(st.empty())//若栈为空,则跳出弹出循环
break;
}
}
return res;
}
};
方法3:使用栈实现的迭代方法3
主要思路:
(1)使用栈实现的中序遍历,具体见代码细节;
/**
* 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) {
if(root==NULL)
return vector<int>();
stack<TreeNode*>st;
vector<int> res;
TreeNode* cur_node=root;
//注意这里的终止条件和方法2的变化
while(cur_node!=NULL||!st.empty()){
//将左结点都压入到栈中
while(cur_node!=NULL){
st.push(cur_node);
cur_node=cur_node->left;
}
//弹出栈顶的元素
cur_node=st.top();
st.pop();
res.push_back(cur_node->val);
//处理右结点
cur_node=cur_node->right;
}
return res;
}
};
上一篇: python实现AI聊天机器人详解流程
下一篇: Javascript 解构赋值详情