题解 | #二叉树的前序遍历#
二叉树的前序遍历
https://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector
*/
vector<int> preorderTraversal(TreeNode* root) {
// write code here
stack<TreeNode*> ST;
vector<int> vec;
if(root){
ST.push(root);
}
while(!ST.empty()){
TreeNode *node =ST.top();
//当前栈顶
ST.pop();
vec.push_back(node->val);
//存放栈顶元素
if(node->right){
ST.push(node->right);
}
if(node->left){
ST.push(node->left);
}
//因为栈，先进后出，根左右，要想在处理完根后先处理左，那么就是先把右压进栈。
}
return vec;
}
};
非递归法，用栈和vector容器。
if(root){
ST.push(root);
}
先处理根。入栈。
while(!ST.empty()){
TreeNode *node =ST.top();
//当前栈顶
ST.pop();
vec.push_back(node->val);
//存放栈顶元素
if(node->right){
ST.push(node->right);
}
if(node->left){
ST.push(node->left);
}
//因为栈，先进后出，根左右，要想在处理完根后先处理左，那么就是先把右压进栈。
}
return vec;
在处理之时，此时栈内元素是根，如何处理，前序根左右，先存根， TreeNode *node =ST.top(); vec.push_back(node->val);放入vector;然后出栈 ST.pop(); 接下来要处理左支，当时栈的特殊性，先入栈左支节点的话，那就是压在了右支节点的下面，取不出来。要想先处理左支，还是得先入栈右支。先出栈左支先存。按此逻辑下去，当处理左支的时候，左支的根节点出栈存vector，需要判断左支节点是否有左右孩子，如果有还是需要按照根左右，先入栈。一层层下去。直到叶子节点，没有左右孩子时。那么此时叶子节点存vector后出栈，没有孩子节点没有入栈。这次就是返回到上一次。看栈中的当前栈顶元素。一般是两种情况，一种是，叶子节点的兄弟节点，也就是右节点，此时仍然按照根左右进行。另一种，当前叶子就是父节点的右节点。那么说明当前叶子的父节点这一支都已经遍历完成，可以向上，父节点的兄弟节点或者更上一层。
华为HUAWEI工作强度 1383人发布
查看19道真题和解析