leetcode-树 tree

2020-05-01

字数统计: 4.3k字 | 阅读时长≈ 21分钟

树

二叉树的定义

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

指针和引用

// 引用是对象的别名，引用不能为空
int a=1;
int& b=a; //定义了b为a的引用
//使用引用的函数传值
void swapint(int& a,int& b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
//调用该函数的c++方法为：swapint(x,y); c++自动把x,y的地址作为参数传递给swapint函数
//使用指针的函数传值
void swapint(int *a,int *b)
{
    int temp;
    temp=*a;
    a=*b;
    *b=temp;
}
//调用该函数的c++语句为：swapint(&x,&y);

递归

递归中遇到需要对每次的结果+=的情况，不能定义变量然后 t1+=dfs(); 而是应该在return的时候写，比如return dfs(root->left)+1。
二叉树的遍历

二叉树的迭代法前、中、后序遍历的整体架构都是一样的，都是while(cur||!s.empty())里面套着一个while(cur)。前、中、后序遍历依赖stack，层次遍历依赖queue。
数的题的易错案例

[]、[1]、[1,null,2]、[1,2]
字典树模板

¶104 二叉树的最大深度(easy)

递归，一次AC

别人的代码：c++使用Math.max()取最大值

¶110 平衡二叉树(easy)

自己迭代迭的乱七八糟

别人的代码：设置一个bool型的全局变量result，迭代中可以修改这个变量。

¶543 二叉树的直径(easy)

自己没思路。

使用递归，由叶子结点到根结点，每个结点都返回自己所能贡献的最大直径。设一个全局变量用来在过程中更新diameter。

¶226 翻转二叉树(easy)

递归，一次AC。

¶617 合并二叉树(easy)

递归。后面的部分看了标程才写出来。

¶112 路径总和(easy)

递归。看了标程才懂。走一步，减一步。

¶437 路径总和3(easy)

双重递归。一个递归遍历整棵树，用来转换root节点；另一个递归用来返回子树的路径数。

¶572 另一个树的子树(easy)

双重递归，一发AC。

别人的，主代码写的更简洁一点

1	return isSubtreeWithRoot(s, t) \|\| isSubtree(s.left, t) \|\| isSubtree(s.right, t);

¶101 对称二叉树(easy)

很简单。==注意判空的顺序！==先判if(!t1&&!t2)，再判if((!t1&&t2)||(!t2&&t1)||(t1->val!=t2->val))，否则就出bug了。

¶111 二叉树的最小深度(easy)

很简单，一发AC。

¶404 左叶子之和(easy)

看了别人的代码才会做。自己写的只能过一半case。

¶687 最长同值路径(easy)

看了讲解视频后自己写出来了。

dfs子函数中return的是当前连续相同路径（不拐弯），全局变量ans中保存的是历史最大路径。

对递归的用法进一步加深。

¶337 打家劫舍(medium)

看了视频讲解。分类讨论根结点是否被抢。先写出递归，再改成动态规划（后根遍历），否则会TLE。

¶671 二叉树中第二小的节点(easy)

自己写的，用的后根遍历，AC。

别人的代码，一个节点要么具有 0 个或 2 个子节点，如果有子节点，那么根节点是最小的节点。

¶144 二叉树的前序遍历(medium)

自己写的，递归。

看了别人的，用栈实现迭代法。

二叉树的迭代法前、中、后序遍历的整体架构都是一样的，都是while(cur||!s.empty())里面套着一个while(cur)。

注意想象绵羊教授做的整个动态过程，先遍历左边同时放入结果和栈，直到没有左子树时pop节点访问其右子树。

¶145 二叉树的后序遍历(medium)

自己写的，递归。

看解析，迭代：从前序遍历到后序遍历：先交换访问左右子树的顺序，然后将整个的结果反转。

1
2
3

前序遍历：center -> left -> right
先变为： center -> right -> left 
再反转：left -> right -> center

反转可以通过函数。也可以将vector变为deque，原来是push_back，现在是push_front。

¶94 二叉树的中序遍历(medium)

看了讲解才会的。

先一直走左子树走到头，然后再pop。

¶637 二叉树的层平均值(easy)

看了解析，第一次做BFS，BFS要用queue，并且需要size记录每层的个数，这样才知道要pop几个。

¶513 找树左下角的值(medium)

BFS，自己AC，注意左下角的值不一定是左子树的值。

看了别人的代码，比我简洁好多。注意调整左右子树入队的顺序，然后合理放置出队的时机，画图模拟一下。

¶669 修剪二叉搜索树(easy)

二叉搜索树的左子树的值都小于根结点，右子树的值都大于根结点。

使用递归。

¶230 二叉搜索树中第k小的元素(medium)

中序遍历二叉搜索树会得到从小到大的排列。

自己一发AC。就是写了一遍中序遍历。

¶538 把二叉搜索树转换为累加树(easy)

中序遍历的变种，自己一发AC。

也可以用递归的方法，先遍历右子树。

¶235 二叉搜索树的最近公共祖先(easy)

自己一发AC，是669题的变形。

¶236 二叉树的最近公共祖先(medium)

看了讲解，递归。分别取root的左子树的结果，以及root的右子树的结果。如果p和q分别在两个子树，则返回root；如果p和q在同一个子树，则返回那个子树的结果。递归的结束条件是root为空或root等于p或q。

¶108 将有序数组转换为二叉搜索树(easy)

自己是有点递归的思路的，不过还是看了别人的代码。

以后遇到递归还是先考虑单独写一个函数吧，思考起来也清晰一点。

¶109 有序链表转换二叉搜索树(medium)

和108题的区别在于，链表不像数组那样可以方便的找到中间的那个数。

所以问题变为，如何找到链表的中间节点。

快慢指针法，有两个指针fast和slow，fast每次走两步，slow每次走一步，当fast->next==NULL||fast->next->next==NULL时，slow指的就是中间节点。

以后注意不管是链表还是树，写while(fast&&fast->next)这种判断的时候都先加上fast再去判断他的节点是否为空吧，这次就因为这个bug卡了一小时。

¶653 两树之和IV-输入BST(easy)

对二叉搜索树中序遍历，得到值从小到大的向量。一前一后两个指针检查和是否等于k。

¶530 二叉搜索树的最小绝对差(easy)

自己一发AC，和上一题思路类似。

¶501 二叉搜索树中的众数(easy)

思路比较简单，代码比较繁琐。

¶208 实现Trie（前缀树）(medium)

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。前缀树，根结点不存数据，其他节点需要存储字符和数字，这个数字是0或1，用来标记这个节点是否可以作为字符串的结尾。

注意要写析构函数，因为节点是动态分配内存的，如果只是把树删掉，而没有析构函数的话，会造成内存泄漏。

智能指针，会自动delete，包含在头文件<memory>中，shared_ptr、unique_ptr、weak_ptr。智能指针不能通过赋值的方式创建，需要按对象的方式创建，使用get()方法获取指针。

1
2
3

// 通过原始指针创建 unique_ptr
std::unique_ptr<TrieNode> root(new TrieNode());
TrieNode* cur=root.get();

¶677 键值映射(medium)

可以用两个哈希表，也可以一个哈希表+一个前缀树，还可以纯用前缀树。

两个哈希表：一个哈希表键为word，值为val；另一个哈希表键为前缀，值为前缀和。

哈希表+前缀树：前缀树代替第一种方法中的后一个哈希表。

纯前缀树：求sum的时候需要递归。

代码

// 104
#include <math.h>
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};
// 110
#include <math.h>
class Solution {
public:
    bool result=true;
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        max_deep(root);
        return result;
    }
    int max_deep(TreeNode* root){
        if(!root) return 0;
        int l1=max_deep(root->left);
        int l2=max_deep(root->right);
        if(abs(l1-l2)>1) result=false;
        return max(l1,l2)+1;
    }
};
// 543
#include <math.h>
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter=0;
        dfs(root, &diameter);
        return diameter;
    }
    int dfs(TreeNode* root,int* diameter){
        if(!root) return 0;
        int l1=dfs(root->left,diameter);
        int l2=dfs(root->right,diameter);
        *diameter = max(*diameter,l1+l2);
        return max(l1,l2)+1;
    }
};
// 226
TreeNode* invertTree(TreeNode* root) {
    if(!root || (!root->left && !root->right)) return root;
    TreeNode* temp=root->right;
    root->right=invertTree(root->left);
    root->left=invertTree(temp);
    return root;
}
// 617
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if(!t1) return t2;
    if(!t2) return t1;
    TreeNode* node=new TreeNode(t1->val+t2->val);
    node->left=mergeTrees(t1->left,t2->left);
    node->right=mergeTrees(t1->right,t2->right);
    return node;
}
// 112
bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && root->val==sum) return true;
        return hasPathSum(root->left,sum- root->val)||hasPathSum(root->right,sum-root->val);
    }
//437
class Solution {
public:
    int ans=0;
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        pathSum(root->left,sum);
        pathSum(root->right,sum);
        dfs(root,sum);
        return ans;
    }
    int dfs(TreeNode* root,int sum){
        if(!root) return 0;
        if(root->val==sum) ans++;
        dfs(root->left,sum-root->val);
        dfs(root->right,sum-root->val);
        return 0;
    }
};
//572
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s||!t) return false;
        if(isSubtree(s->left,t)) return true;
        if(isSubtree(s->right,t)) return true;
        return sametree(s,t);

    }
    bool sametree(TreeNode* s, TreeNode* t){
        if(!s&&!t) return true;
        if((!s&&t)||(!t&&s)||(s->val!=t->val)) return false;
        return sametree(s->left,t->left) && sametree(s->right,t->right);
    }
};
// 101
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return sametree(root->left,root->right);
    }
    bool sametree(TreeNode* t1, TreeNode* t2){
        if(!t1&&!t2) return true;
        if((!t1&&t2)||(!t2&&t1)||(t1->val!=t2->val)) return false;
        return sametree(t1->left,t2->right)&&sametree(t1->right,t2->left);
    }
};
// 111
int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left &&root->right) return minDepth(root->right)+1;
        if(!root->right&&root->left) return minDepth(root->left)+1;
        return min(minDepth(root->left),minDepth(root->right))+1;
    }
// 404
class Solution {
public:
    int ans=0;
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        if(isleaf(root->left)) return root->left->val+sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
    bool isleaf(TreeNode* root){
        if(!root) return false;
        if(!root->left&&!root->right) return true;
        return false;
    }
};
//687
#include <math.h>
class Solution {
public:
    int ans=0;
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root){
        if(!root||(!root->left&&!root->right)) return 0;
        int t1=dfs(root->left);
        int t2=dfs(root->right);
        int leftPath=(root->left&&root->val==root->left->val)?t1+1:0;
        int rightPath=(root->right&&root->val==root->right->val)?t2+1:0;
        ans=max(ans,leftPath+rightPath);
        return max(leftPath,rightPath);
    }
};
//337
#include <math.h>
class Solution {
public:
    int rob(TreeNode* root) {
        int* ans=postRoot(root);
        return max(ans[0],ans[1]);
    }
    int* postRoot(TreeNode* root){
        if(!root) return new int [] {0,0};
        int* l = postRoot(root->left);
        int* r = postRoot(root->right);
        int* res = new int[2];
        res[0] = max(l[0],l[1])+max(r[0],r[1]);
        res[1] = l[0]+r[0]+root->val;
        return res;
    }
};
//671
int findSecondMinimumValue(TreeNode* root) {
    if(!root||(!root->left&&!root->right)) return -1;
    int left = root->left->val;
    int right = root->right->val;
    if(root->val==left) left = findSecondMinimumValue(root->left);
    if(root->val==right) right = findSecondMinimumValue(root->right);
    if(left!=-1&&right!=-1) return min(left,right);
    if(left==-1) return right;
    return left;
}
//144
//递归：
class Solution {
public:
    vector<int> ans;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root) ans.push_back(root->val);
        else 
        {
            return ans;
        }
        ans = preorderTraversal(root->left);
        ans = preorderTraversal(root->right);
        return ans;
    }
};
//迭代
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* cur=root;
    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            res.push_back(cur->val);
            cur=cur->left;
        }
        cur=s.top()->right;
        s.pop();
    }
    return res;
}
//145
//递归：
class Solution {
public:
    vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return ans;
        ans = postorderTraversal(root->left);
        ans = postorderTraversal(root->right);
        ans.push_back(root->val);
        return ans;
    }
};
//迭代
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    deque<int> res;
    TreeNode* cur = root;
    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            res.push_front(s.top()->val);
            cur=cur->right;
        }
        cur=s.top()->left;
        s.pop();
    } 
    return vector<int>(res.begin(),res.end());
}
//94
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> temp;
    TreeNode* cur = root;
    while(cur||!temp.empty())
    {
        while(cur)
        {
            temp.push(cur);
            cur=cur->left;
        }
        cur = temp.top();
        ans.push_back(cur->val);
        temp.pop();
        cur=cur->right;
    }
    return ans;
}
//637
vector<double> averageOfLevels(TreeNode* root) {
    vector<double> res;
    if(!root) return res;
    queue<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        int size=s.size();
        double sum=0;
        for(int i=0;i<size;i++)
        {
            TreeNode* cur=s.front();
            sum+=(cur->val);
            s.pop();
            if(cur->left) s.push(cur->left);
            if(cur->right) s.push(cur->right);
        }
        res.push_back(sum/size);
    }
    return res;
}
//513
int findBottomLeftValue(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        root = q.front();
        q.pop();
        if(root->right) q.push(root->right);
        if(root->left) q.push(root->left);
    }
    return root->val;
}
//669
TreeNode* trimBST(TreeNode* root, int L, int R) {
    if(!root) return NULL;
    if(root->val < L) return trimBST(root->right,L,R);
    if(root->val > R) return trimBST(root->left,L,R);
    root->left = trimBST(root->left,L,R);
    root->right = trimBST(root->right,L,R);
    return root;
}
//230
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> s;
    vector<int> res;
    TreeNode* cur=root;
    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        s.pop();
        res.push_back(cur->val);
        cur=cur->right;
    }
    return res[k-1];
}
//538
TreeNode* convertBST(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur=root;
    int t=0;
    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->right;
        }
        cur=s.top(); s.pop();
        cur->val+=t;
        t=cur->val;
        cur=cur->left;
    }
    return root;
}
//236
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root||root==p||root==q) return root;
    TreeNode* left=lowestCommonAncestor(root->left,p,q);
    TreeNode* right=lowestCommonAncestor(root->right,p,q);
    if(!left) return right;
    if(!right) return left;
    return root;
}
//108
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return BST(nums,0,nums.size());
    }
    TreeNode* BST(vector<int>& nums,int L,int R){
        if(L>=R) return NULL;
        int n=(R+L)/2;
        TreeNode *root=new TreeNode(nums[n]);
        root->left=BST(nums,L,n);
        root->right=BST(nums,n+1,R);
        return root;
    }
};
//109
TreeNode* sortedListToBST(ListNode* head) {
    if(!head) return NULL;
    if(!head->next) return new TreeNode(head->val);
    ListNode *fast=head, *slow=head;
    ListNode *prev=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        prev=slow;
        slow=slow->next;
    }
    TreeNode *root=new TreeNode(slow->val);
    prev->next=NULL;
    root->left=sortedListToBST(head);
    root->right=sortedListToBST(slow->next);
    return root;
}
//653
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> ans;
        inorder(root,ans);
        int i=0, j=ans.size()-1;
        if(2*ans[0]>k||2*ans[j]<k) return false;
        while(i!=j)
        {
            int temp=ans[i]+ans[j];
            if(temp==k) return true;
            if(temp>k) j--;
            else i++;
        }
        return false;
    }
    void inorder(TreeNode* root, vector<int>& res){
        if(!root) return;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
};
//530
#include <math.h>
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        int mmin=res[res.size()-1];
        for(int i=0;i<res.size()-1;i++)
        {
            mmin = min(mmin,res[i+1]-res[i]);
        }
        return mmin;
    }
    void inorder(TreeNode* root,vector<int>& res){
        if(!root) return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
};
//501
#include <math.h>
class Solution {
public:
    TreeNode *prev=NULL;
    int temp;
    int num=1;
    int maxnum=1;
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
    void inorder(TreeNode* root, vector<int>& res){
        if(!root) return ;
        inorder(root->left,res);
        if(!prev) 
        {
            prev=root;
            res.push_back(prev->val);
        }
        else
        {
            if(root->val==prev->val)
                num++;
            else
            {
                prev=root;
                num=1;
            } 
            if(num>maxnum)
                while(!res.empty()) res.pop_back();
            if(num>=maxnum) 
            {
                res.push_back(root->val);
                maxnum=max(num,maxnum);
            }
        }
        inorder(root->right,res);
    }
};
//208
class Trie {
private:
    struct TrieNode{
        bool isword;
        vector<TrieNode*> child;
        TrieNode():isword(false), child(26,nullptr){}
        ~TrieNode(){
            for(TrieNode* node:child)
                if(node) delete node;
        }
    };
    TrieNode* find(const string& word){
        TrieNode* cur=root_.get();
        for(char c:word){
            if(cur->child[c-'a'])
                cur=cur->child[c-'a'];
            else return nullptr;
        }
        return cur;
    }
public:
    std::unique_ptr<TrieNode> root_;
    /** Initialize your data structure here. */
    Trie(): root_(new TrieNode()) {}
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* cur=root_.get();
        for(char c:word){
            if(!cur->child[c-'a'])
                cur->child[c-'a']=new TrieNode();
            cur=cur->child[c-'a'];
        }
        cur->isword=true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* cur=find(word);
        if(cur&&cur->isword) return true;
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return find(prefix)!=nullptr;
    }
};
//677 
class MapSum {
private:
    struct TrieNode
    {
        int val;
        vector<TrieNode*> child;
        TrieNode():val(0), child(26,nullptr){}
        ~TrieNode(){
            for(auto c:child)
                if(c!=nullptr) delete c;
        }
    };
public:
    /** Initialize your data structure here. */
    std::unique_ptr<TrieNode> root_;
    unordered_map<string, int> vals_;
    MapSum(): root_(new TrieNode()) {}
    
    void insert(string key, int val) {
        TrieNode *cur=root_.get();
        int cha=val-vals_[key];
        vals_[key]=val;
        for(auto c:key)
        {
            if(cur->child[c-'a']==nullptr) 
                cur->child[c-'a']=new TrieNode();
            cur=cur->child[c-'a'];
            cur->val+=cha;
        }
    }
    
    int sum(string prefix) {
        TrieNode *cur=root_.get();
        for(auto c:prefix)
        {
            cur=cur->child[c-'a'];
            if(cur==nullptr) return 0;
        }
        return cur->val;
    }    
};