leetcode笔记_树

2024-01-04 15:55:16

树

树的遍历

前序遍历

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

 

中序遍历

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

 

后序遍历

/**
 * 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 postOrder(TreeNode* root,vector<int>& res)
    {
        if(root==nullptr)
            return;
        postOrder(root->left,res);
        postOrder(root->right,res);
        res.push_back(root->val);
​
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> arr;
        postOrder(root,arr);
        return arr;
​
    }
};

 

层序遍历

/**
 * 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<vector<int>> res;
        if(root==nullptr)
            return res;
        
        queue<TreeNode*> qu;
        qu.push(root);
        int level=0;
        while(!qu.empty())
        {
            level++;
            vector<int> levevRes; 
            //每一层的个数等于当前的队列长度
            
            int levelSize=qu.size();           
            for(int i=0;i<levelSize;i++)
            {
                TreeNode* cur=qu.front();
                levevRes.push_back(qu.front()->val);
                qu.pop();
                if(cur->left)
                {
                    qu.push(cur->left);
                    
                }
                if(cur->right)
                {
                    qu.push(cur->right);
                   
                }
            }
          res.push_back(levevRes);  
        }
        return level;
​
​
​
    }
};

 

运用递归解决问题

二叉树树的深度

/**
 * 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) {
         vector<vector<int>> res;
        if(root==nullptr)
            return 0;
        
        queue<TreeNode*> qu;
        qu.push(root);
        int level=0;
        while(!qu.empty())
        {
            level++;
            vector<int> levevRes; 
            //每一层的个数等于当前的队列长度
            
            int levelSize=qu.size();           
            for(int i=0;i<levelSize;i++)
            {
                TreeNode* cur=qu.front();
                levevRes.push_back(qu.front()->val);
                qu.pop();
                if(cur->left)
                {
                    qu.push(cur->left);
                    
                }
                if(cur->right)
                {
                    qu.push(cur->right);
                   
                }
            }
          res.push_back(levevRes);  
        }
        return level;
    }
};

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

/**
 * 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 isSymmetric(TreeNode* root) {
        return check(root,root);
    }
    bool check(TreeNode*left,TreeNode*right)
    {
        if(left==nullptr&&right==nullptr)
        {
            return true;
        }
        if(left==nullptr||right==nullptr)
        {
            return false;
        }
        return (left->val==right->val)&&check(left->left,right->right)&&check(left->right,right->left);
    }
};

 

路径总和

/**
 * 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 hasPathSum(TreeNode* root, int targetSum) {
        //如果根节点为空返回false
        if(root==nullptr)
            return false;
        //如果左右都为空此时的总和就是到叶子结点的路径和
        if(root->left==nullptr&&root->right==nullptr)
            return root->val==targetSum;
        return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
​
    }
};

 

总结

从前序遍历与后序遍历构造二叉树

/**
 * 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0)
            return nullptr;
        
        return dfs(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
        
​
    }
    
    //中序遍历的根节点在中间
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder,int inStart,int inEnd,int postStart,int postEnd){
        if(inStart>inEnd)
            return nullptr;
        //树的根节点的后序遍历的最后一个结点
        TreeNode* root=new TreeNode(postorder[postEnd]);
        //TreeNode* root=new TreeNode(20);
            //如果中序遍历的头和尾都相等，则说明已经访问完，返回这棵树
        if(inStart==inEnd)
            return root;
        
        
        //以根节点的值为中心，左右两边分别是根节点的子树的结点
        int mid=0;
        //从当前中序遍历的数组的第一个点开始搜索，直到找到根节点
        while((root->val)!=inorder[inStart+mid])mid++;
        //左子树是根节点中序遍历左边那部分
        root->left= dfs(inorder,postorder,inStart,inStart+mid-1,postStart,postStart+mid-1);
        //右子树是根节点中序遍历右边那部分
        root->right=dfs(inorder,postorder,inStart+mid+1,inEnd,postStart+mid,postEnd-1);
        return root;
        
    }
};

 

从前序遍历与中序遍历构造二叉树

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //如果前序遍历或者中序遍历长度为0或者长度不相等，树不存在
        int prelen=preorder.size();
        int inlen=inorder.size();
        if(prelen==0||inlen==0||prelen!=inlen)
            return nullptr;
        return dfs(preorder,inorder,0,prelen-1,0,inlen-1);




    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder,int preStart,int preEnd,int inStart,int inEnd)
    {
        //如果坐标越界返回空值
        if(preStart>preEnd)
            return nullptr;
        //根节点是先序遍历的第一个结点
        TreeNode* root=new TreeNode(preorder[preStart]) ;
        //如果两者相等，说明遍历完了这棵树，返回根节点
        if(preStart==preEnd)
            return root;
        //找到中序遍历中和根节点相同的结点的相对坐标,mid-1其实就是左子树的结点个数
        int mid=0;
        while(root->val!=inorder[inStart+mid])mid++;
        //中序遍历中根节点两边分别为左右子树
        root->left=dfs(preorder,inorder,preStart+1,preStart+mid,inStart,inStart+mid-1);
        root->right=dfs(preorder,inorder,preStart+mid+1,preEnd,inStart+mid+1,inStart);
        return root;
    }
};

 

填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        //如果根节点为空返回root
        if(root==nullptr)
            return nullptr;
        //把根节点的左右结点连接
        dfs(root->left,root->right);
        return root;


    }
    void dfs(Node* left,Node* right)
    {
        //如果左右结点有空值，返回nullptr
        if(left==nullptr||right==nullptr)
            return;
        //把左右结点连起来

        left->next=right;
        dfs(left->left,left->right);
        dfs(left->right,right->left);
        dfs(right->left,right->right);
    }
};

 

填充每个节点的下一个右侧节点指针 II

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root==nullptr)
            return nullptr;
        if(root->left!=nullptr)
        {
            //如果左右孩子不为空，左孩子指向右孩子
            if(root->right!=nullptr)
            {
                root->left->next=root->right;
            }
            //左孩子不为空，右孩子为空，左孩子指向父节点的next结点的最左边那个孩子
            else{
                root->left->next=getFirstChild(root->next);
            }
        }
        //右孩子不为空那就让右孩子连接
        if(root->right!=nullptr)
        {
            root->right->next=getFirstChild(root->next);
        }
        //再连接左子树和右子树
        //要先连接右子树，才能确保找到next结点
        connect(root->right);
        connect(root->left);
        return root;

    }
    //用于获取当前结点的最左边的孩子结点
    Node* getFirstChild(Node* root){
        if(root==nullptr)
            return nullptr;
        //左孩子不为空，返回左孩子
        if(root->left!=nullptr)
            return root->left;
        //左孩子不为空，右孩子为空，返回右孩子
        if(root->right!=nullptr)
            return root->right;
        //否则再搜索下一个结点
        return getFirstChild(root->next);

    }
};

 

二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //如果root是空或者两个节点有一个结点为根节点，那就直接返回根节点
        //因为此时根节点就是最近公共祖先
        if(root==nullptr||root==p||root==q)
            return root;
        //否则就找左右子树里pq的最近公共祖先
        TreeNode*left=lowestCommonAncestor(root->left,p,q);
        TreeNode*right=lowestCommonAncestor(root->right,p,q);
        //如果左孩子找不到pq的话说明在右孩子上
        if(left==nullptr)
            return right;
        //如果右孩子找不到pq那就说明在左孩子上
        if(right==nullptr)
            return left;
        //如果左右孩子都找到了说明一个在左孩子一个在右孩子上。返回当前结点即可
        return root;



    }
};

 

二叉树的序列化和反序列化

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 TreeNode* node;
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        node=root;
        return "";

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

  • 写了一个晚上没写出来，看到题解我惊呆了

  • 我思路是把原来结点转化为前序遍历和中序遍历，然后根据中序遍历和前序遍历来转化成原来的数，但是一直有问题，明天再看看问题在哪

  • 还看到用层序遍历存树然后再还原的，这个也好牛呀

上一篇：王道2.3.7综合应用题


下一篇：Codeforces Global Round 15部分题解（A-D）