[Leetcode] Binary tree preorder traversal

576 0 0

作者:王大咩的图书馆

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

For example:
Given binary tree{1,#,2,3},

return[1,2,3].

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

二叉树的遍历分为：先序遍历、中序遍历、后续遍历，三者的分类可以根据根节点被访问的先后顺序来区分。

先序遍历的遍历顺序是根节点->左孩子->右孩子。思路：先将根节点存入栈中，然后首先访问根节点的值，接下来在root沿着左孩子访问（更新根节点为root->left）的同时，将对应的右孩子依次存入栈中，直到root到达最左端的左孩子（root->left不存在），一旦左孩子不存在，就从栈中取出结点访问，利用栈的先进后出的特性，访问右孩子（即root=S.top()），然后重复上述过程，实现先序遍历。可以举例证明，整棵树的根结点最后出栈。代码如下：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> preorderTraversal(TreeNode *root) 
13     {
14         vector<int> res;
15         if(root==nullptr)    return res;
16         stack<TreeNode*> S;
17         S.push(root);
18         while( !S.empty())
19         {
20             res.push_back(root->val);
21             if(root->right)      //避免右孩子为空
22                 S.push(root->right);
23             if(root->left)
24                 root=root->left;
25             else
26             {
27                 root=S.top();
28                 S.pop();
29             }
30 
31         }
32 
33         return res;
34 
35     }
36 };

虽然题目要求不能用递归版的，但是写在这方便以后查看：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) 
    {
        vector<int> res;
        RecursiveTra(root,res);
        return res;
    }
    void RecursiveTra(TreeNode *rot,vector<int> &res)
    {
        if(root==NULL)  return;
        res.push_back(root->val);
        RecursiveTra(root->left,res);
        RecursiveTra(root->right,res);
    }
};

内容来源于网络如有侵权请私信删除

标签：算法数据结构 LeetCode

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

[Leetcode] Binary tree preorder traversal