二叉树先序遍历

爱被打了一巴掌 2022-05-16 12:52 155阅读 0赞

下面是leetcode上的一道题，先序遍历二叉树。

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?

对于二叉树的遍历，很容易联想到递归，那么第一种思路就是使用递归的思想，参考代码如下：

/**
     * 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> result;
            helper(root,result);
            return result;
     
        }
        void helper(TreeNode *node,vector<int> &result){
            if (node==NULL){
                return;
            }
            result.push_back(node->val);
            helper(node->left,result);
     
            helper(node->right,result);
        }
    };

我们再司考一下，先序遍历就是根节点、左子节点、右子节点，那么也可以通过ADT栈来实现。

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