C#和.Net框架

遍历

前序遍历

递归

class Solution {
public:
    void preorder(TreeNode* root,vector<int>& v)
    {
        if(root)
        {
            v.push_back(root->val);
            preorder(root->left,v);
            preorder(root->right,v);
        }
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        preorder(root,v);
        return v;
    }
};

非递归

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return {};
        stack<TreeNode*> st;
        vector<int> v;
        st.push(root);
        while(!st.empty())
        {
            root = st.top();
            st.pop();
            v.push_back(root->val);
            // 注意入栈的时候先右后左
            if(t->right)
                st.push(root->right);
            if(t->left)
                st.push(root->left);
        }
        return v;
    }
};

Mirros

• 有时间再学

  中序遍历

  递归

  class Solution {
  public:
    void inorder(TreeNode* root,vector<int>& v)
    {
        if(root)
        {
            inorder(root->left,v);
            v.push_back(root->val);
            inorder(root->right,v);
        }
    }
  
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        inorder(root,v);
        return v;
    }
  };
  

  非递归

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

  Mirros

• 有时间再学

后续遍历

递归

class Solution {
public:
    void postOrder(TreeNode* root,vector<int>& v)
    {
        if(root)
        {
            postOrder(root->left,v);
            postOrder(root->right,v);
            v.push_back(root->val);
        }
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        postOrder(root,v);
        return v;
    }
};

非递归

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* prev = nullptr;
        while(root != nullptr || !st.empty())
        {
            while(root != nullptr)
            {
                st.push(root);
                root = root->left;
            }

            root = st.top();
            st.pop();
            if(root->right == nullptr || root->right == prev)
            {
                v.push_back(root->val);
                prev = root;
                root = nullptr;
            }
            else
            {
                st.push(root);
                root = root->right;
            }
        }
        return v;
    }
};