二叉树的遍历

标签：node 遍历 TreeNode st 二叉树 push root result

先序遍历非递归
算法1

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;
    }
};

---

算法2

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;     } };

 

 

标签：node,遍历,TreeNode,st,二叉树,push,root,result
From： https://www.cnblogs.com/laojiahuo/p/17837554.html