数据结构

二叉树

Posted by 云起 on 2022-10-10
Estimated Reading Time 4 Minutes
Words 745 In Total
Viewed Times

二叉树

遍历

先序遍历

根-左-右

递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
void pre(TreeNode*root,vector<int>& res){
        if(root==nullptr) return ;
        res.push_back(root->val);
        pre(root->left,res);
        pre(root->right,res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        pre(root,res);
        return res;
    }

非递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return  res;
        stack<TreeNode*> st;
        while(root!=nullptr||!st.empty()){
            while(root!=nullptr){
            res.push_back(root->val);
            st.push(root);
            root=root->left;
            }
            root=st.top();
            st.pop();
            root=root->right;
        }
        return res;
    }

中序遍历

左-根-右

递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
void inorder(TreeNode *root,vector<int>& res){
        if(root==nullptr) return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);

    }
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> res;
        inorder(root,res);
        return res;
    }

非递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        while(root!=nullptr|| !st.empty()){
            while(root!=nullptr)
            {
                st.push(root);
                root=root->left;
            }
            root=st.top();
            st.pop();
            res.push_back(root->val);
            root=root->right;
        }
        return res;
    }

后序遍历

左-右-根

递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
void post(TreeNode* root,vector<int>& res){
        if(!root) return ;
        post(root->left,res);
        post(root->right,res);
        res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        post(root,res);
        return res;
    }

非递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> postorderTraversal(TreeNode* root) {
      stack<TreeNode*> st;
      TreeNode* pre;//pre标记右子树是否被访问过
      vector<int> res;
      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==pre)
          {
              res.push_back(root->val);
              pre=root;
              root=nullptr;
          }
          else{
              st.push(root);
              root=root->right;
          }
      }
      return res;
   }

层序

按层遍历

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
         if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;
            int len=q.size();
            for(int i=0;i<len;++i){
                TreeNode* r=q.front();
                tmp.push_back(r->val);
                q.pop();
                if(r->left){
                q.push(r->left);
            }
            if(r->right){
                q.push(r->right);
            }
            }
            ans.push_back(tmp);
        }
        return ans;
    }

随写

二叉搜索树

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

验证方法

中序非递归

时间复杂度O(n) 空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        stack<int> va;
        while(root||!st.empty()){
            while(root){
                st.push(root);
                root=root->left;
            }
            root=st.top();
            st.pop();
            if(!va.empty()){
                if(va.top()>=root->val) return false;
                va.pop();
                va.push(root->val);
            }
            else va.push(root->val);
            root=root->right;
        }
        return true;
    }

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
数据结构
FRIENDS
ESC