讨论/《二叉树》 - 二叉树的前序遍历/
《二叉树》 - 二叉树的前序遍历

C++先序遍历递归写法:

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        dfs(root,ret);  // 先序遍历递归函数
        return ret;
    }

    void dfs(TreeNode* root, vector<int> &ret){
        if(root == nullptr){
            return;
        }
        ret.push_back(root->val);   // 记录 先序遍历 的顺序
        dfs(root->left,ret);
        dfs(root->right,ret);
    }

C++先序遍历非递归写法:

// 先序遍历,非递归实现
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* p = root;
        vector<int> ret;
        if(root != nullptr){
            stack<TreeNode*> st;
            st.push(p);         // 根结点入栈
            while( !st.empty() ){
                p = st.top();   // 在栈中弹出一个结点,并且记录这个结点值
                st.pop();
                
                ret.push_back(p->val);

                if(p->right != nullptr){    // 先压右子树
                    st.push(p->right);
                }
                if(p->left != nullptr){     // 压入左子树 
                    st.push(p->left);
                }
            }
        }
        return ret;
    }
展开全部 39 讨论