本文共 1250 字，大约阅读时间需要 4 分钟。

Difficulty: 中等

给你二叉树的根节点 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

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

Solution

Language: ****

class Solution {
   public:typedef TreeNode Node;    vector
   
     preorderTraversal(TreeNode* root) {
           vector
    
      res;        while(root) {
               if(root->left==NULL) {
                   res.push_back(root->val);                root = root->right;                //左子树空，遍历右边子树            }else{
                   //左子树不空                Node* f = getLeftMostRight(root);                if(f->right == root) {
                       f->right  = NULL;                    root = root->right;                }else {
                       res.push_back(root->val);                    f->right = root;                    root = root->left;                }            }        }        return res;    }    Node* getLeftMostRight(Node* root ) {
           // if(root==NULL) return NULL;        Node * f = root->left;        while(f && f->right && f->right!=root) {
               f = f->right;        }        return f;    }};​
    
   

转载地址：http://zbyzi.baihongyu.com/