[leetcode]binary-tree-preorder-Traversal

偏执的太偏执、 2022-03-20 05:50 146阅读 0赞

## 题目描述： ##

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

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

## 实现思路： ##

要实现非递归的二叉树前序遍历，可以借助栈来实现，前序遍历是根-左-右，先把根压栈然后弹出到vector中，再依次将右孩子压栈、左孩子压栈，然后迭代进行，每次都弹出栈底的结点~

## 具体实现： ##

/**
     * 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;
            if(!root){
                return res;
            }
            stack<TreeNode *> st;
            st.push(root);
            while(st.size()){
                TreeNode * temp;
                temp = st.top();
                res.push_back(temp->val);
                st.pop();
                if(temp->right){
                    st.push(temp->right);
                }
                if(temp->left){
                    st.push(temp->left);
                }
            }
            return res;
        }
    };

[leetcode]binary-tree-preorder-Traversal

发表评论取消回复

还没有评论，来说两句吧...

相关阅读