leetcode 树 简单题

发表于 | 更新于 | 分类于 ，
本文字数： 103k

589. N叉的前序遍历

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int>res;
    vector<int> preorder(Node* root) {
        if (root == nullptr) return res;
        res.push_back(root->val);
        if(root->children.size() == 0) return res;
        else {
            for(auto child:root->children) {
                preorder(child);
            }
            return res;
        }
    }
};

897. 递增顺序查找树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode* temp;
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* res = new TreeNode();
        temp = res;
        dfs(root);
        return res->right;
    }
    void dfs(TreeNode * root) {
        if (root == nullptr) return;
        else {
            TreeNode * l = root->left;
            TreeNode * r = root->right;
            dfs(l);
            temp->right = root;
            root->left = nullptr;
            temp = temp->right;
            dfs(r);
        }
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int>vec;
    int kthLargest(TreeNode* root, int k) {
        dfs(root);
        return vec[k - 1];
    }
    void dfs(TreeNode * root) {
        if (!root) return;
        dfs(root->right);
        vec.push_back(root->val);
        dfs(root->left);
    }
};

110. 平衡二叉树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root) >=0;
    }
    int dfs(TreeNode * root) {
        if (!root) return 0;
        int h_l = dfs(root->left);
        int h_r = dfs(root->right);
        if (h_r  == -1 || h_l == -1 || abs(h_l - h_r) > 1)return -1;
        else return 1 + max(h_l,h_r);
    }
};

112. 路径总和

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int flag, cnt;
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        dfs(root,targetSum);
        return flag;
    }
    void dfs(TreeNode * root, int targetSum) {
        if(!root) return ;
        cnt+= root->val;
        if (!root->left && !root->right) {
            if (cnt == targetSum) flag = 1;
            cnt-= root->val;
            return ;
        }
        dfs(root->left,targetSum);
        dfs(root->right,targetSum);
        cnt-= root->val;
    }
};

官方题解bfs；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        queue<TreeNode *> que_node;
        queue<int> que_val;
        que_node.push(root);
        que_val.push(root->val);
        while (!que_node.empty()) {
            TreeNode *now = que_node.front();
            int temp = que_val.front();
            que_node.pop();
            que_val.pop();
            if (now->left == nullptr && now->right == nullptr) {
                if (temp == sum) return true;
                continue;
            }
            if (now->left != nullptr) {
                que_node.push(now->left);
                que_val.push(now->left->val + temp);
            }
            if (now->right != nullptr) {
                que_node.push(now->right);
                que_val.push(now->right->val + temp);
            }
        }
        return false;
    }
};

1022. 从根到叶的二进制数之和

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int ans;
    int sumRootToLeaf(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode * root,int cnt) {
        if (!root) return;
        if (!root->left && !root->right) {
            ans += (cnt * 2 + root->val);
            return ;
        }
        dfs(root->left, cnt * 2 + root->val);
        dfs(root->right, cnt * 2 + root->val);
        return;
    }
};

和上一题类似，显然这题也可以用bfs

606. 根据二叉树创建字符串

code

这题有点垃圾，题意含糊不清；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string res = "";
    string tree2str(TreeNode* t) {
        if (t == nullptr) return res;
        dfs(t);
        return res;
    }
    void dfs(TreeNode * t){
        res = res + to_string(t->val);
        if (t->left)  {
            res += '(';
            dfs(t->left);
            res += ')';
        }
        if (t->right) {
            if (!t->left) res += "()";
            res += '(';
            dfs(t->right);
            res += ')';
        }
        return ;
    }
};

617. 合并二叉树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1)return t2;
        if(!t2)return t1;
        dfs(t1,t2);
        return t1;
    }
    void dfs(TreeNode* t1, TreeNode* t2){
        if(t1 && t2) {
            t1->val += t2->val;
            dfs(t1->left,t2->left);
            dfs(t1->right,t2->right);
            if (!t1->left && t2->left)
                t1->left = t2->left;
            if (!t1->right && t2->right)
                t1->right = t2->right;
        }
        return;
    }
};

104. 二叉树的最大深度

code

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return dfs(root);
    }
    int dfs(TreeNode * root) {
        if (!root) return 0;
        else return 1 + max(dfs(root->left),dfs(root->right));
    }
};

当然还可以用bfs求；

102. 二叉树的层序遍历

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>res;
        if (root == nullptr) return res;
        vector<int>temp1;
        queue<TreeNode *>temp2;
        temp2.push(root);
        while(!temp2.empty()){
            temp1.clear();
            int cnt = temp2.size();
            for(int i = 0; i < cnt; i++) {
                TreeNode * temp = temp2.front();
                temp2.pop();
                temp1.push_back(temp->val);
                if (temp->left) {
                    temp2.push(temp->left);
                }
                if (temp->right){
                    temp2.push(temp->right);
                }
            }
            res.push_back(temp1);
        }
        return res;
    }
};

dfs版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        dfs(root,1);
        return res;
    }
    void dfs(TreeNode * root, int dep) {
        if (!root) return ;
        if (dep > res.size()) {
            vector<int > temp(0,0);
            res.push_back(temp);
        }
        res[dep-1].push_back(root->val);
        dfs(root->left, dep + 1);
        dfs(root->right, dep + 1);
    }
};

107. 二叉树的层序遍历 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>>res;
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        dfs(root,1);
        reverse(res.begin(),res.end());
        return res;
    }
    void dfs(TreeNode * root, int dep) {
        if (!root) return ;
        if (dep > res.size()) {
            vector<int > temp(0,0);
            res.push_back(temp);
        }
        res[dep-1].push_back(root->val);
        dfs(root->left, dep + 1);
        dfs(root->right, dep + 1);
    }
};

226. 翻转二叉树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root) {
        if(!root)return;
        dfs(root->left);
        dfs(root->right);
        swap(root->left,root->right);
    }
};

235. 二叉搜索树的最近公共祖先

code

官方题解，需要注意这是一颗二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode *res = root;
        while(true) {
            if (p->val < res->val && q->val < res->val) {
                res = res->left;
            }else if (p->val > res->val && q->val > res->val) {
                res = re->right;
            }else break;
        }
        return res;
    }
};

100. 相同的树

code

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && q || !q && p) return 0;
        if (!p && !q) return 1;
        if (p->val != q->val) return 0;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

530. 二叉搜索树的最小绝对差

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxm = 0x3f3f3f, temp = maxm;
    int getMinimumDifference(TreeNode* root) {
        dfs(root);
        return maxm;
    }
    void dfs(TreeNode * root) {
        if (!root) return ;
        dfs(root->left);
        maxm = min(maxm,abs(temp - root->val));
        temp = root->val;
        dfs(root->right);
    }
};

404. 左叶子之和

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int res = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode * root) {
        if (!root)return ;
        TreeNode* rl = root->left;
        if (rl && !rl->left && !rl->right) res += rl->val;
        dfs(root->left);
        dfs(root->right);
        return ;
    }
};

965. 单值二叉树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int val;
    bool isUnivalTree(TreeNode* root) {
        val = root->val;
        return dfs(root);
    }
    int dfs(TreeNode * root) {
        if (!root) return 1;
        if (root->val != val) return 0;
        return dfs(root->left) && dfs(root->right);
    }
};

669. 修剪二叉搜索树

这里注意引用的使用，引用和指针是不一样的；把dfs函数里的*、&改成*就错了；

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        dfs(root,low,high);
        return root;
    }
    void dfs(TreeNode* &root, int low, int high) {
        if (!root) return ;
        if (root->val < low) {
            root = root->right;
            dfs(root,low,high);
        } else if(root->val > high) {
            root = root->left;
            dfs(root,low,high);
        } else {
            dfs(root->left,low,high);
            dfs(root->right,low,high);
        }
        return ;
    }
};

993. 二叉树的堂兄弟节点

code

啊啊啊，看我这丑陋的代码，太糟糕了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        int pre_x,pre_y;
        queue<TreeNode *>q;
        q.push(root);
        while(!q.empty()) {
            pre_x = pre_y = 0;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode * temp = q.front();
                q.pop();
                TreeNode *rl = temp->left;
                TreeNode *rr = temp->right;
                if (rl) {
                    q.push(rl);
                    if (rl->val == x)
                        pre_x = temp->val;
                    if (rl->val == y) 
                        pre_y = temp->val;
                }
                if (rr) {
                    q.push(rr);
                    if (rr->val == x)
                        pre_x = temp->val;
                    if (rr->val == y)
                        pre_y = temp->val;
                }
            }
            if (pre_x != pre_y && pre_x!=0 && pre_y!=0)
                return 1;
        }
        return 0;
    }
};

653. 两数之和 IV - 输入 BST

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    set<int>s;
    bool findTarget(TreeNode* root, int k) {
        return dfs(root, k);
    }
    int dfs(TreeNode * root, int k) {
        if (!root) return 0;
        if (s.count(k - root->val))
            return 1;
        else s.insert(root->val);
        return dfs(root->left, k) || dfs(root->right, k);
    }
};

543. 二叉树的直径

code

dfs版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int res = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode * root) {
        if (!root) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        res = max(res, l + r);
        return max(l, r) + 1;
    }
};

671. 二叉树中第二小的节点

题解

对于这颗特殊的二叉树，需要求第二小的数；

由题意，根一定是最小的，记录下根的数值\(a\)，搜索这棵树，找满足大于\(a\)的最小值；

一开始思路错了，其实如果在搜索过程中把子树的最小值返回也是一样的，如果根的两个子树的最小值相同，那就需要递归的到两颗子树里面找；

注意下面代码的第三行minm = 1ll << 32，因为minm是long long，如果是int，左移最多只能进行31次，否则会报错；因此需要写成1ll；

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long minm = 1ll <<32,low;
    int findSecondMinimumValue(TreeNode* root) {
        if (!root)return -1;
        low = root->val;
        dfs(root);
        return minm == 1ll <<32?-1:minm;
    }
    void dfs(TreeNode * root) {
        if (!root) return ; 
        if (root->val > low && root->val != minm)
                minm = min(minm, 1ll * root->val);
        dfs(root->left);
        dfs(root->right);
        return ;
    }
};

637. 二叉树的层平均值

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<double> res;
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) return res;
        queue<TreeNode *>q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode * temp = q.front();
                q.pop();
                sum += temp->val;
                if (temp->left)
                    q.push(temp->left);
                if (temp->right)
                    q.push(temp->right);
            }
            res.push_back(sum / size);
        }
        return res;
    }
};

559. N 叉树的最大深度

code

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        queue<Node *>q;
        q.push(root);
        int dep = 0;
        while(!q.empty()) {
            int size = q.size();
            dep ++;
            for (int i = 0; i <size; i++) {
                Node *p = q.front();
                q.pop();
                for (auto child:p->children) {
                    q.push(child);
                }
            }
        }
        return dep;
    }
};

dfs

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        if (!root->children.size()) return 1;
        int maxm = 0;
        for (auto child:root->children) {
            maxm = max(maxm, 1 + maxDepth(child));
        }
        return maxm;
    }
};

面试题 04.02. 最小高度树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode * res;
        if(!nums.size()) return NULL;
        int n = nums.size();
        build(res, 0, n - 1, nums);
        return res;
    }
    void build(TreeNode * &res, int l, int r, vector<int>& nums) {
        if (l > r) {
            return ;
        }
        else {
            int mid = (l + r) >> 1;
            res = new TreeNode(nums[mid]);
            build(res->left, l, mid - 1, nums);
            build(res->right, mid + 1, r, nums);
            return ;
        }
    }
};

700. 二叉搜索树中的搜索

code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return NULL;
        if (root->val == val) return root;
        else {
            TreeNode * l = searchBST(root->left, val);
            TreeNode * r = searchBST(root->right, val);
            if (!l) return r;
            else return l;
        }
    }
};

938. 二叉搜索树的范围和

code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        int ans = 0;
        if (root->val <= high && root->val >= low) ans += root->val;
        if (root->val >= low) ans += rangeSumBST(root->left, low, high);
        if (root->val <= high) ans += rangeSumBST(root->right, low, high);
        return ans;
    }
};

111. 二叉树的最小深度

code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        TreeNode * l = root->left;
        TreeNode * r = root->right;
        if(!l && !r) return 1;
        if (l && r) return 1 + min(minDepth(l), minDepth(r));
        return 1 + minDepth(l?l:r);
    }
};

590. N叉树的后序遍历

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int>res;
    vector<int> postorder(Node* root) {
        dfs(root);
        return res;
    }
    void dfs(Node * root) {
        if(!root)return;
        for (auto child:root->children) {
            dfs(child);
        }
        res.push_back(root->val);
        return ;
    }
};

872. 叶子相似的树

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> sle[2];
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        dfs(root1,0);
        dfs(root2,1);
        if(sle[0] != sle[1]) return 0;
        else return 1;
    }

    void dfs(TreeNode * root, int i) {
        if (!root) return ;
        if (!root->left && !root->right) {
            sle[i].push_back(root->val);
            return ;
        }
        dfs(root->left,i);
        dfs(root->right,i);
    }
};

257. 二叉树的所有路径

使用to_string()将数字转化为字符串，(char)(number + '0')这种方法只使用于一位正数；

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> ans;
    vector<string> binaryTreePaths(TreeNode* root) {
        count(root, "");
        return ans;
    }
    void count(TreeNode * root, string temp) {
        if (!root) return ;
        if (!root->left && !root->right) {
            ans.push_back(temp + to_string(root->val));
            return ;
        }
        count(root->left, temp + to_string(root->val) + "->");
        count(root->right, temp + to_string(root->val) + "->");
    }
};

563. 二叉树的坡度

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int ans = 0;
    int findTilt(TreeNode* root) {
        countval(root);
        return ans;
    }
    int countval(TreeNode* root) {
        if (!root) return 0;
        int vl = countval(root->left);
        int vr = countval(root->right);
        ans += abs(vl-vr);
        return vl + vr + root->val;
    }
};

572. 另一个树的子树

写了一个比较好想的方法，官方题解放了kmp、树哈希之类的；

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<TreeNode *>res;
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s || !t) return 0;
        find(t, s);
        TreeNode * st = t;
        if (!res.size()) return 0;
        else {
            for (auto x: res) {
                if (check(st, x))
                    return 1;
            }
            return 0;
        }
    }
    int check(TreeNode* s, TreeNode* t) {
        if (!s && t || s && !t) return 0;
        if (!s && !t) return 1;
        if (s->val == t->val) 
            return check(s->left, t->left) && check(s->right, t->right);
        else return 0;
    }
    void find(TreeNode * s, TreeNode * t) {
        if (!s || !t) return ;
        if (s->val == t->val)
            res.push_back(t);
        find(s, t->left);
        find(s, t->right);
        return ;
    }
};

236. 二叉树的最近公共祖先

code

写了一个比较笨的方法，就是统计根节点到要查询的节点的路径，然后从根节点进行比较，找到第一个不同的父节点之前的父节点即为答案；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    TreeNode* sp[10004];
    TreeNode* sq[10004];
    int i, j;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        findpath(root, p, sp, &i);
        findpath(root, q, sq, &j);
        TreeNode* pre = root;
        for (int k = 0; k < i && k < j; k++) {
            if (sp[k]->val == sq[k]->val) pre = sp[k];
            else break;
        }
        return pre;
    }
    int findpath(TreeNode* root, TreeNode* f, TreeNode* s[], int *n) {
        if (!root) return 0;
        s[(*n)++] = root;
        if (root->val == f->val)    return 1;
        int l = findpath(root->left,f, s, n);
        int r = findpath(root->right, f, s, n);
        if (!l && ! r) {
            (*n)--;
            return 0;
        }else return 1;
    }
};

这是官方解，当发现p和q分别位于某个子树的两个分支里时，那么当前节点就是他们的最近公共祖先；

还一种方法是用map记录路径；

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if (root->val == p->val || root->val == q->val)
            return root;
        TreeNode * l = lowestCommonAncestor(root->left, p, q);
        TreeNode * r = lowestCommonAncestor(root->right, p, q);
        if(!l) return r;
        if(!r) return l;
        return root;
    }
};