[数据结构与算法]2021-07-28

树的问题2：

二叉树的前序遍历 
morris遍历//非递归式遍历法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
         vector<int>ans;
         while(root!=nullptr){
             if(root->left==nullptr){
                 ans.push_back(root->val);
                 root=root->right;//z左子树为空，直接处理右子树
             }else{
                 TreeNode*pre=root->left;
                 while(pre->right!=nullptr&&pre->right!=root){
                     pre=pre->right;//找前驱
                 }
                 if(pre->right==nullptr){
                     ans.push_back(root->val);
                     pre->right=root;
                     root=root->left;//第一次遍历，黑边处理左子树
                 }else{
                     pre->right=nullptr;
                     root=root->right;//第二次还原处理右子树
                 }
             }
         }
         return ans;
    }
};


递归遍历法
class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

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

用栈遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == NULL) return {};
        stack<TreeNode*> s;
        vector<int> ans;
        s.push(root);
        while(!s.empty()){
            TreeNode* node = s.top();
            ans.push_back(node->val);
            s.pop();
            if(node->right) s.push(node->right);
            if(node->left) s.push(node->left);
        }
        return ans;
    }
};

后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void add_ans(TreeNode*p,vector<int>&ans){
        stack<int>sta;
        while(p!=nullptr){
            sta.push(p->val);
            p=p->right;
        }
        while(!sta.empty()){
            ans.push_back(sta.top());
            sta.pop();
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
            vector<int>ans;
            TreeNode*p=new TreeNode(0);
            p->left=root;
            while(p!=nullptr){
                if(p->left==nullptr){
                    p=p->right;
                }else{
                    TreeNode*pre=p->left;
                    while(pre->right!=nullptr&&pre->right!=p){
                         pre=pre->right;
                    }
                    if(pre->right==nullptr){
                        pre->right=p;
                        p=p->left;
                    }else{
                        pre->right=nullptr;
                        add_ans(p->left,ans);
                        p=p->right;
                    }
                }
            }
        return ans;
    }
};

树的问题往往用递归解决

/**leetcode100相通树
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr&&q==nullptr) return true;
        if(p&&q){
          if(p->val!=q->val){
              return false;
          }
          if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right)) return true;
        }
        return false;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */对称树
class Solution {
public:
    bool duichen(TreeNode*root1,TreeNode*root2){
        if(root1==nullptr&&root2==nullptr) return true;
        if(root1==nullptr||root2==nullptr) return false;
        if(root1->val!=root2->val) return false;
        if(duichen(root1->left,root2->right)&&duichen(root1->right,root2->left)){
           return true;
        }          
           return false;
        }
    bool isSymmetric(TreeNode* root) {
       if(!root) return true;
       return duichen(root->left,root->right);
    }
};

二叉树层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
            vector<int>vec;
            vector<vector<int>>v;
            if(!root) return v;
            queue<TreeNode*>que; 
            que.push(root);
            while(!que.empty()){
                int size=que.size();
                for(int i=0;i<size;i++){
                     TreeNode*temp=que.front();
                     vec.push_back(temp->val);
                     que.pop();
                     if(temp->left) que.push(temp->left);
                     if(temp->right) que.push(temp->right);
                }
                v.push_back(vec);
                vec.clear();
            }   
        return v; 
    }
};

二叉树锯齿形输出
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(!root) return ans;
        queue<TreeNode*>q,next;
        vector<int>temp;
        q.push(root);
        while(!q.empty()){
            TreeNode*node=q.front();
            q.pop();
            temp.push_back(node->val);
            if(node->left) next.push(node->left);
            if(node->right) next.push(node->right);
            if(q.empty()){
                ans.push_back(temp);
                temp.clear();
                q.swap(next);
            }
        }
        for(int i=0;i<ans.size();i++){
            if(i%2==1){
                std::reverse(ans[i].begin(),ans[i].end());
            }
        }
        return ans;
    }
};

#二叉树最大层数
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
            if(!root) return 0;
            return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};


二叉树最小深度
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (!root ) {
            return 0;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }
        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }
        return min_depth + 1;
    }
};

有序链表转换为二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
TreeNode*func(vector<int>&num,int l,int r){
          if(l>r){
              return nullptr;
          }
          int mid=(l+r)/2;
          TreeNode*p=new TreeNode(num[mid]);
          p->left=func(num,l,mid-1);
          p->right=func(num,mid+1,r);
          return p;
      }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
       TreeNode*root=func(nums,0,nums.size()-1);
        return root;
    }
};

//直接由定义法
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

      TreeNode*func(vector<int>&num,int l,int r){
          if(l>r){
              return nullptr;
          }
          int mid=(l+r)/2;
          TreeNode*p=new TreeNode(num[mid]);
          p->left=func(num,l,mid-1);
          p->right=func(num,mid+1,r);
          return p;
      }
    TreeNode* sortedListToBST(ListNode* head) {
        TreeNode*root=func(nums,0,nums.size()-1);
        return root;
    }
};