题目链接：Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},

   1 
    \ 
     2 
    / 
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

这道题的要求是前序遍历二叉树。

二叉树，即每个节点下面最多有2个子节点的树。

  1. 递归遍历

递归遍历二叉树，比较简单。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> vi;
        preorderTraversal(root, vi);
        return vi; 
    }
private:
    void preorderTraversal(TreeNode *root, vector<int> &vi)
    {
        if(root != NULL)
        {
            vi.push_back(root -> val);
            preorderTraversal(root -> left, vi);
            preorderTraversal(root -> right, vi);
        }
    }
};

  1. 迭代遍历

用栈进行存储，根节点先入栈。然后不断读取栈顶元素并弹栈，读取某一节点的时候，并记录该节点，如果存在右子树，说明需要后遍历右子树，因此右子节点先入栈。如果存在左子树，左子节点入栈。这样，直到栈为空。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> vi;
        
        if(root == NULL)
            return vi;
        
        stack<TreeNode *> stp;
        stp.push(root);
        while(!stp.empty())
        {
            TreeNode *p = stp.top();
            vi.push_back(p -> val);
            stp.pop();
            
            if(p -> right != NULL)
                stp.push(p -> right);
            
            if(p -> left != NULL)
                stp.push(p -> left);
        }
        
        return vi; 
    }
};

  1. Morris Traversal方法

该方法只需要O(1)空间，而且同样可以在O(n)时间内完成遍历二叉树。

  1. 如果当前节点（cur）的左子树为空（cur->left==NULL），则输出当前节点（cur->val）并将其右子树作为当前节点（cur=cur->right）。
  2. 如果当前节点的左子树不为空（cur->left!=NULL），在当前节点的左子树中找到当前节点在中序遍历下的前驱节点（pre）。(1)如果前驱节点的右子树为空（pre->right==NULL），将它的右子树设置为当前节点（pre->right=cur）。输出当前节点（cur->val，在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左子树（cur=cur->left）。(2)如果前驱节点的右子树为当前节点（pre->right==cur），将它的右子树重新设为空（pre->right=NULL，恢复树的形状）。当前节点更新为当前节点的右子树（cur=cur->right）。
  3. 重复以上1、2直到当前节点为空。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution
{
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> vi;
        
        TreeNode *cur = root, *pre = NULL;
        while(cur != NULL)
        {
            if(cur -> left == NULL)
            {
                vi.push_back(cur -> val);
                cur = cur -> right;
            }
            else
            {
                pre = cur -> left;
                while(pre -> right != NULL && pre -> right != cur)
                    pre = pre -> right;
                
                if(pre -> right == NULL)
                {
                    pre -> right = cur;
                    vi.push_back(cur -> val);
                    cur = cur -> left;
                }
                else
                {
                    pre -> right = NULL;
                    cur = cur -> right;
                }
            }
        }
        
        return vi; 
    }
};

详见这里。