JZTXT

二叉树的遍历

发布时间 2023-11-16 23:36:24作者: 老家伙2004
先序遍历非递归
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

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