leetcode 144 二叉树的前序遍历

前序遍历的递归解法：

方法一C++:

 1 /**
 2  * Definition for a binary tree node.
 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         preorder(root,res);
16         return res;
17     }
18     void preorder(TreeNode* root,vector<int> &res){
19         if(root==NULL) return;
20         res.push_back(root->val);
21         if(root->left) preorder(root->left,res);
22         if(root->right) preorder(root->right,res);
23     }
24 };

前序遍历的非递归方法：

前序遍历和层序遍历的迭代写法很相似，因此也较为简单。

前序遍历采用stack，当栈顶元素p非空，前序遍历先访问栈顶元素并pop()，然后依次压入右孩子和左孩子。

层序遍历采用queue, 当队首元素p非空，层序遍历先访问队首元素并pop()，然后依次压入左孩子和右孩子。

C++代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

/**
使用stack完成前序的递归过程，与层序类似，不过采用stack，
每一个循环中，访问栈顶元素，而且先push(p->right)在push(p->left);
**/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==NULL) return {};
        vector<int> res;
        stack<TreeNode*>s;
        TreeNode* p=root;
        s.push(p);
        while(!s.empty()){
            p=s.top();
            res.push_back(p->val);
            s.pop();
            
            if(p->right) s.push(p->right);
            if(p->left) s.push(p->left);
        }
        return res;
    }
};

leetcode 144 二叉树的前序遍历

相关推荐