题解 | #二叉树的前序遍历#
二叉树的前序遍历
http://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635
题意：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
方法一：
递归
思路：核心：先序递归要按照“根节点->左儿子->右儿子”的顺序遍历树。
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
pre(root);//先序遍历
return res;
}
void pre(TreeNode *root){//递归先序遍历
if(root==nullptr)
return;
res.push_back(root->val);
pre(root->left);
pre(root->right);
}
};
时间复杂度：%2C%E6%A0%91%E7%9A%84%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E9%83%BD%E8%A6%81%E8%AE%BF%E9%97%AE%E3%80%82)
空间复杂度：%EF%BC%8C%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%EF%BC%9A%E5%8D%95%E6%94%AF%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E6%A0%88%E6%B7%B1%E5%BA%A6%E4%B8%BAO(n)%E3%80%82)
方法二：
栈实现非递归
思路：栈实现先序遍历。
初始化一个存储树节点的栈空间，遍历指针 p=root。
外层循环的条件是遍历指针 p 非空或栈非空，
内层循环则是从根节点开始，循环的遍历左儿子入栈；
当左儿子为空时，则弹栈并指向弹出元素的右儿子。
其中，入栈序列则是树的先序遍历序列。
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;//栈
TreeNode* p=root;
while(p||!st.empty()){//循环
while(p){//遍历左儿子入栈
st.push(p);
res.push_back(p->val);
p=p->left;
}
p=st.top();//弹栈
st.pop();
p=p->right;//遍历右儿子
}
return res;
}
};
时间复杂度：空间复杂度：%EF%BC%8C%E6%9C%80%E5%9D%8F%E6%83%85%E5%86%B5%EF%BC%9A%E5%8D%95%E6%94%AF%E6%A0%91%E7%9A%84%E6%A0%88%E7%A9%BA%E9%97%B4%E4%B8%BAO(n)%E3%80%82)
中国农业银行工作强度 73人发布
查看6道真题和解析