树的三种遍历：递归+非递归

深藏阁楼爱情的钟 2023-01-22 11:47 26阅读 0赞

[牛客网][Link 1]

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    
    class Solution { 
    public:
        
        vector<int> v1;
        vector<int> v2;
        vector<int> v3;
        
        TreeNode* fistOr(TreeNode* r){ 
            if(r!=nullptr){ 
                v1.push_back(r->val);
                fistOr(r->left);
                fistOr(r->right);
            }
            return nullptr;
        }
        
        TreeNode* midOr(TreeNode* r){ 
            if(r!=nullptr){ 
                midOr(r->left);
                v2.push_back(r->val);
                midOr(r->right);
            }
            return nullptr;
        }
        
        TreeNode* backOr(TreeNode* r){ 
            if(r!=nullptr){ 
                backOr(r->left);
                backOr(r->right);
                v3.push_back(r->val);
            }
            return nullptr;
        }
        
        vector<vector<int> > threeOrders(TreeNode* root) { 
            
            fistOr(root);
            midOr(root);
            backOr(root);
            return { move(v1),move(v2),move(v3)};
        }
        
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        
        vector<int> v1;
        vector<int> v2;
        vector<int> v3;
        
        bool fistOr(TreeNode* r){ 
            
            stack<TreeNode*>st;
            if(r!=nullptr){ 
                st.push(r);
            }
            
            while(!st.empty()){ 
                
                auto t = st.top();
                v1.push_back(t->val);
                st.pop();
                if( t->right!=nullptr ){ 
                    st.push(t->right);
                }
                if( t->left!=nullptr ){ 
                    st.push(t->left);
                }
            }
            
            return true;
        }
        
        bool midOr(TreeNode* r){ 
            stack<TreeNode*>st;
            if( r!=nullptr ){ 
                st.push(r);
                auto tp = r;
                while(tp->left != nullptr){ 
                    st.push(tp->left);
                    tp = tp->left;
                }
            }
            
            while(!st.empty()){ 
                auto tp = st.top();
                st.pop();
                v2.push_back(tp->val);
                if( tp->right!=nullptr ){ 
                    tp = tp->right;
                    st.push(tp);
                    while(tp->left != nullptr){ 
                        st.push(tp->left);
                        tp = tp->left;
                    }
                }
            }
            return true;
        }
        
        bool backOr(TreeNode* r){ 
            stack<TreeNode*>st;
            if( r!=nullptr ){ 
                st.push(r);
                auto tp = r;
                while(tp->left != nullptr){ 
                    st.push(tp->left);
                    tp = tp->left;
                }
            }
            
            TreeNode* lasto = nullptr;
            while( !st.empty()){ 
                auto tp = st.top();
                //debug(tp->val)
                tp = st.top();
                //debug(00)
                //debug(st.size())
                if( tp->right == nullptr || tp->right == lasto ){ 
                    v3.push_back(tp->val);
                    //debug(111)
                    st.pop();
                    lasto = tp;
                }
                else{ 
                    tp = tp->right;
                    st.push(tp);
                    //debug(222)
                    
                    while(tp->left != nullptr){ 
                        st.push(tp->left);
                        tp = tp->left;
                    }
                }
            }
            return true;
        }
        
        vector<vector<int> > threeOrders(TreeNode* root) { 
            
            fistOr(root);
            midOr(root);
            backOr(root);
            return { move(v1),move(v2),move(v3)};
        }
        
    };

![在这里插入图片描述][20210520100458675.png]

LeetCode题解

[Link 1]: https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=196&tqId=37153&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking&tab=answerKey
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221020/5742e714001c4af1bf55b53ff58ef9c1.png
[20210520100458675.png]: /images/20221020/e29d67e61fbd4d6483cfda2a5448fb2c.png