做网站的私活排名怎么优化快
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
递归思路
先树根，然后左子树，然后右子树。每棵子树递归。解题步骤：
1.先将根节点值放入容器;
2.接着将左子树的节点值放入容器;
3.再将右子树的节点值放入容器具体代码实现：
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(!root) return preVec;preVec.emplace_back(root->val); //先将根节点值放入容器preorderTraversal(root->left); //接着将左子树的节点值放入容器preorderTraversal(root->right);//再将右子树的节点值放入容器return preVec;}
private:vector<int> preVec;
};迭代算法思路
由于每棵子树都先访问其根节点。对节点的左右子树来说，也一定是先访问根。因此，每到一个节点Node，就应该立即访问它本身。
又因为在Node的两棵子树中，遍历完左子树后，再遍历右子树。因此，在访问完根节点后，遍历左子树前，要将右子树压入栈。解题步骤：
1.先将节点本身的值放入容器;
2.接着将右子节点放入栈中；
3.接着遍历左子树节点，即更新左子树节点为当前节点;
4.当左子树遍历到叶节点后，开始异栈顶元素为当前元素，并弹出该栈顶元素(右节点);
5.若栈中弹出的元素非空，则执行1～4；若为空，则不进行任何处理，继续弹出栈顶元素；
6.直至站内元素和当前元素为空，此时，返回容器。具体代码实现：
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(!root) return {};stack<TreeNode* > preStk;vector<int> preVec;TreeNode* current = root;while(current || preStk.size()) {while(current) {preVec.emplace_back(current->val);preStk.push(current->right);current = current->left;}current = preStk.top();preStk.pop();}return preVec;}
};AC结果
