发表于 | 分类于

Diameter Of Tree(找到树中两个叶节点的最远距离)

题目描述：

给定一棵树的头结点，找到树中的两个节点，要求这两个节点的距离最大，返回该距离。

解题思路：

通过分析我们可以知道，一棵树的两个节点的最远距离可能来自两种情况：

  • 左节点的最深深度 + 右节点的最深深度，经过根节点；
  • 在左节点为根节点中的两个节点存在最远距离；在右节点为根节点中的两个节点存在最远距离；

我们用height函数找到某个节点的深度；用diameter函数找到以某个节点为根中两个叶节点的最远距离。

代码如下：

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
/**
 * 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:
    int diameterOfBinaryTree(TreeNode* root) {
        if (root == NULL) return 0;
        
        int lh = height(root->left);
        int rh = height(root->right);
        //找到左右节点的最深深度
        
        int ld = diameterOfBinaryTree(root->left);
        int rd = diameterOfBinaryTree(root->right);
        //找到左右节点各自为根中的最远距离
        
        return max(lh + rh, max(ld, rd));
        //返回这两种情况中的最远距离即可
    }
    int height(TreeNode* head){
        if (head == NULL) return 0;
        return 1 + max(height(head->left), height(head->right));
        //递归找到最深深度
    }
};

发表于 | 分类于

Path Question In Tree

题目描述1：

给定一棵树的头结点和一个目标值；判断是否树中存在一条从根到叶的路径，其路径上节点和的值为目标值。

例子：

这题是leetcode上的题目，可以看这上面的题目描述.

解题思路：

主要的思路还是递归来解决这道题目。我们在不断的遍历树的过程中，对sum值进行改变，即减去当前遍历节点上的值；如果遇到了当前是叶节点，并且其值和当前的目标值相同，就直接返回true.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root)
            return false;
            //如果是空节点，返回false
        if (root->left == NULL && root->right == NULL)
            return root->val == sum ? true : false;
            //如果是叶节点，判断和当前sum的关系
        if (root){
            if (hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
                return true;
        }
        //如果不是叶节点，就递归遍历左右节点，只要有一个是true即可
        return false;
        
    }
};

题目描述2：

给定一棵树的头结点和一个目标值；找到树中所有从根到叶节点和为目标值的情况并返回。

例子：

leetcode上的题目描述

解题思路：

本题的思路在与使用回溯的方法；但是需要注意的点是什么时候回溯。我们用一个vector保存当前路径的节点；用一个vector保存每次符合条件后保存路径。

代码如下：

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
/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> list;//保存当前路径
        vector<vector<int>> res;//保存符合条件的路径
        findPath(root, list, sum, res);
        return res;
    }
    void findPath(TreeNode* head, vector<int>& list, int target, vector<vector<int>>& res){
        if (!head) return;//如果是空节点直接返回
        
        list.push_back(head->val);//将当前节点保存到路径中
        if (!head->left && !head->right && head->val == target)
            res.push_back(list);
            //如果是叶节点，并且符合条件，将其保存到结果中
        findPath(head->left, list, target - head->val, res);
        findPath(head->right, list, target- head->val, res);
        list.pop_back();
        //如果是叶节点，不管是不是符合条件都会进入这个流程；但是叶节点的左右都是空，直接返回，最后一句话进行了回溯
    }
};

题目描述3:

给定一棵树的头节点和一个目标值，要求返回树中任意从父节点到子节点路径和为目标值的个数。

例子:

这题也是leetcode上的题目，详情可见此处.

解题思路：

当然这题的思路依旧是递归的方式；但是有不同的是，我们需要判断在遍历到当前节点的时候，其遍历的路径上的子路径是否存在符合条件的情况。所以我们主要是用一个vector保存了遍历到当前节点的路径上的累加和；这样我们就可以通过遍历累加和数组来判断当前路径上是否存在符合要求的路径。

代码如下:

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
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        //空节点直接返回0
        vector<int> path{0};
        //先在路径和数组中放入0，用来表示从根节点开始的情况
        int res = 0;
        //保存符合条件的情况个数
        helper(root, path, sum, res);
        return res;
    }
    void helper(TreeNode* root, vector<int> &path, int sum, int &res){
        if (!root) return;
        //如果是空节点直接返回即可
        path.push_back(root->val + path[path.size() - 1]);
        //将当前节点的值和上一个节点的路径和保存到路径和数组中
        int cur = path.back();
        //以当前节点的路径和为标杆
        for (int i = path.size() - 2; i >= 0; i--){
            if (cur - path[i] == sum) res++;
        }
        //遍历数组中是否存在符合条件的情况
        helper(root->left, path, sum, res);
        helper(root->right, path, sum, res);
        //分别遍历左右节点
        path.pop_back();
        //最后记得回溯一步
    }
};

题目描述4：

给定一棵树的头结点，从树的头结点到根节点的每一条路径都代表了一个数，要求返回所有路径代表的数的和。

这道题的具体描述可以看LeetCode129.

解题思路：

主要解题思路也是很直接，我们不断的往树的深度遍历，主要用一个变量来记录每条路径上所代表的数，用一个变量记录所有路径的总和即可。

代码如下：

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
/**
 * 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:
    int sumNumbers(TreeNode* root) {
        int res = 0;
        path(root, 0, res);
        return res;
    }
    void path(TreeNode* root, int cur, int& res){
        if (!root) return;
        if (!root->left && !root->right){
            res = res + cur * 10 + root->val;
            return;
            // 如果是叶节点，我们就将当前路径的数累加
        }
        path(root->left, cur * 10 + root->val, res);
        path(root->right, cur * 10 + root->val, res);
        //分别继续遍历左右节点的路径，用乘以10来代表路径上的10进制数
    }
};

题目描述5：

给定一棵树的头结点，要求返回树中的每一条路径表示，例如1->2->3等。
依旧是LeetCode的题目LeetCode257。具体描述可以看这里。解题思路不再赘述。

代码如下：

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
/**
 * 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:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path = "";
        //代表某条路径
        vector<string> res;
        //保存全部路径
        helper(root, res, path);
        return res;
    }
    void helper(TreeNode* root, vector<string> &vec, string path){
        if (!root){
            return;
        }
        if (!root->left && !root->right){
            vec.push_back(path + to_string(root->val));
            return;
            //碰到叶节点保存结果并返回
        }
        helper(root->left, vec, path + to_string(root->val) + "->");
        helper(root->right, vec, path + to_string(root->val) + "->");
        //继续遍历左右节点，注意"->"加在此处，便于处理叶节点的情况
    }
};

题目描述6:

给定一棵树的头结点，要求返回树的每条路径上各自的最大值。
具体题目描述可以看LeetCode515.
这边代码的解法使用的是按层遍历的方式，找到每一条路径上的数然后保存排序找到最大值；当然也可以直接遍历。

代码如下：

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
36
37
38
39
40
/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> result;
        if (!root) return result;
        queue<TreeNode*> cur;
        queue<TreeNode*> next;
        cur.push(root);
        while(!cur.empty()){
            vector<int> row;
            while(!cur.empty()){
                TreeNode* front = cur.front();
                cur.pop();
                row.push_back(front->val);
                if (front->left) next.push(front->left);
                if (front->right) next.push(front->right);
            }
            res.push_back(row);
            queue<TreeNode*> tmp = cur;
            cur = next;
            next = tmp;
        }
        for (auto vec: res){
            sort(vec.begin(), vec.end());
            result.push_back(vec[vec.size() - 1]);
        }
        return result;
        
    }
};

发表于 | 分类于

Split Array With Equal Sum(四段和相等的切分点)

题目描述：

给定一个长度为n的数组；要求找到3个切分点i,j,k满足如下要求：

  • 0 < i, i + 1 < j, j + 1 < k < n - 1;
  • sum[0, i - 1] = sum[i + 1, j - 1] = sum[j + 1, k - 1] = sum[k + 1, n - 1]

例子：

输入时[1,2,1,2,1,2,1]的符合题意的切分点是[1,3,5],见[LeetCode548]

解题思路：

首先为了计算切分的段落和，我们可以构建一个累加和数组，其中sum[i]代表数组[0,i]的数据和，这样可以计算任意段落的和了；然后我们可以遍历i,j,k不同的位置用来判断是否满足条件即可。需要注意的点有因为数组中可以有负数，所以不能根据累加和肯定递增，如果当前位置不满足条件后面肯定不满足这个想法来剪枝；另外测试用例中包含了大量的0；对于计算累加和的时间消耗太多；所以需要针对这个情况做累加和计算的改进。

代码如下：

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 splitArray(vector<int>& nums) {
        if(nums.size() < 6) return false;
        vector<int> sum;
        int prev = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0 && i > 0 && nums[i - 1] == 0)  continue;
            //针对连续0的情况，累加和计算的改进
            prev += nums[i];
            sum.push_back(prev);
        }
        for (int i = 1; i < sum.size() - 5; i++){
            int sum1 = sum[i - 1];
            for (int j = i + 2; j < sum.size() - 3; j++){
                int sum2 = sum[j - 1] - sum[i];
                if (sum1 != sum2) continue;
                for (int k = j + 2; k < sum.size() - 1; k++){
                    int sum3 = sum[k - 1] - sum[j];
                    int sum4 = sum[sum.size() - 1] - sum[k];
                    if (sum2 == sum3 && sum3 == sum4)
                        return true;
                }
            }//遍历i,j,k用来寻找满足条件的切分位置
        }
        return false;
        
    }
};

发表于 | 分类于

题目描述：

这题来源于LeetCode，具体可以看这里.

解题思路：

第一种解题思路是找到打印的规律；主要有两个地方：

  • 如果是第一行和最后一行，字符串的间隔和nrows有关；间隔为2(nrows - 1);
  • 如果是中间行，其间隔是交替出现规律的；规律并且和所处的行数j有关；对于第j行而言；其下标间隔为2(nrows - 1 - j)和2j交替出现的。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    string convert(string s, int numRows) {
        if (s.size() <= numRows || numRows == 1) return s;
        int interval = 2 * numRows - 2;
        string res;
        for (int i = 0; i < numRows; i++){
            if (i == 0 || i == numRows - 1){
                int j = i;
                res = res + s[j];
                while((j + interval) < s.size()){
                    j += interval;
                    res = res + s[j];
                }//如果是第一行和最后一行的规律
            }else{
                int j = i;
                res = res + s[j];
                bool flag = true;
                while(j < s.size()){
                    if (flag){
                        if ((j + interval - 2 * i) < s.size()){
                            res = res + s[j + interval - 2 * i];
                            j = j + interval - 2 * i;
                            flag = false;
                        }else{
                            break;
                            
                        }
                        //第一种间隔2(nrows - 1 - i)
                    }else{
                        if (j + 2 * i < s.size()){
                            res += s[j + 2 * i];
                            j += 2 * i;
                            flag = true;
                        }else{
                            break;
                        }
                        //第二种规律是2i
                    }
                }
            }
        }
        return res;
    }
};

解题思路2：

第二种解题思路我们可以将每行存入数组，我们遍历字符串，利用标记变量决定存入数组的方式，存入的方式根据锯齿的走向决定向上还是向下；向上走到第0行后就向下；向下走到nrows - 1后就向上走。

代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string res[numRows];
        string result;
        int step = 0;
        int row = 0;
        for (int i = 0; i < s.size(); i++){
            res[row] = res[row] + s[i];//存入数组
            if (row == 0) step = 1;
            if (row == numRows - 1) step = -1; //决定走向
            row = row + step;//数组下标随走向决定
        }
        for (int i = 0; i < numRows; i++){
            result = result + res[i];//将数组连起来返回
        }
        return result;
    }
};

发表于 | 分类于

Longest Uncommon Subsequence(最长非公共子序列)

题目描述：

给定两个字符串，找到两个字符串的最长非公共子序列。其中子序列的定义为：原序列中删除部分字符所得到，即原始序列中的字符顺序不改变。即假设字符串str1和str2。找到str1中的最长子序列，且该序列无法由str2得到。另外我们设定str1和””都是str1的子序列。如果”aa”和”aa”的话，不存在非公共子序列，返回-1.

例子：

“abc”和”cdc”的最长子序列是”abc”(“cdc”)。所以最长的非公共子序列长度为3.见LeetCode521

解题思路：

初看题目会陷入困局；想要找到”abc”中的所有子序列然后和”cdc”一一验证。但是其实我们从另外一个角度看，我们可以先将两个字符串相同的情况排除后;在两个字符串不同长度的情况下，肯定是较长的字符串的本身是我们需要的结果。因为较长的字符串肯定无法通过另外一个串得到，所以较长的串就是我们所求的。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int findLUSlength(string a, string b) {
        if(a == b) return - 1;
        int res = a.size();
        for (int i = 0; i < a.size(); i++){
            for (int j = i; j < a.size(); j++){
                if (sub(a.substr(i, j - i + 1), b)){
                    res = max(res, j - i + 1);
                }
            }
        }//判断str1的子序列是不是str2的子序列
        for (int i = 0; i < b.size(); i++){
            for (int j = i; j < b.size(); j++){
                if (sub(b.substr(i, j - i + 1), a)){
                    res = max(res, j - i + 1);
                }
            }
        }//判断str2的子序列是不是str1的子序列
        return res;
        
    }
    bool sub(string source, string target){
        for (int i = 0; i < source.size(); i++){
            int j = 0;
            while(j < target.size() && target[j] != source[i]){
                j++;
            }
            if (j >= target.size()) return false;
            else{
                j++;
            }
        }
        return true;
        //判断两个串的互为子序列关系
    }
};
class Solution {
public:
    int findLUSlength(string a, string b) {
        return (a == b) ? -1: max(a.size(), b.size());
        //直接返回较长的串的长度即可。
    }
};

Longest Uncommon Subsequence II(最长非公共子序列)

题目描述：

给定一个字符串数组，找到字符串数组中的最长非公共子序列。

例子：

“abc”, “cde”, “fgh”的最长公共子序列的长度是3，任意的一个字符串都是最长非公共子序列。

解题思路：

与上一题类似，我们想直接利用最长的那个字符来作为结果返回；但是”aaa”,”aaa”,”bb”这样的情况导致结果不符合题意；所以需要利用哈希表来过滤掉超过两次的字符串；但是仅仅这样还是不够；因为如果输入是”aaa”,”aaa”,”aa”这样的情况下是不存在所谓的非公共子序列。所以思路是我们找到一个字符串，判断它是否是最长公共子序列的方法是与比它长的字符串比较，只有它不是所有比它长的字符串的子序列才可以成为最长子序列。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool cmp(pair<string, int> &a, pair<string, int>&b){
    return a.first.size() > b.first.size();
}
//作为sort函数的比较；按照字符串的长度排序，由高到低。
bool s1SubOfs2(string s1, string s2){
    int i = 0;
    int j = 0;
    for (;i < s1.size(); i++){
        while(j < s2.size() && s2[j] != s1[i]) j++;
        if (j == s2.size()) return false;
        j++;
    }
    return true;
}
// 判断s1是不是s2的子序列函数
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        unordered_map<string, int> hash;
        vector<pair<string, int>> vec;
        for (auto str : strs) hash[str]++;
        //用哈希表将字符串保存，value是字符串出现的次数
        
        for (auto it = hash.begin(); it != hash.end(); it++){
            vec.push_back(*it);
        }
        //用vector保存string和次数，便于利用cmp函数的排序
        sort(vec.begin(), vec.end(), cmp);
        //利用cmp函数排序
        for (int i = 0; i < vec.size(); i++){
            if (vec[i].second == 1){
            //过滤掉超过两次的字符串
                int j = 0;
                for (; j < i; j++){
                    if (s1SubOfs2(vec[i].first, vec[j].first)) break;
                    //将当前字符串和比它长的串一一比较；
                }
                if (j == i) return vec[i].first.size();
                //当它与比它长的字符串都不是子序列关系后返回
            }
        }
        return -1;
        //如果不存在返回-1.
        
    }
};

发表于 | 分类于

The Type Of Tree

题目描述：

给定一个树的头结点，判断这棵树是不平衡二叉树。平衡二叉树的定义是左右对当前节点而言，左子树和右子树的深度差值不超过1；且左右子树也是平衡二叉树。

解题思路：

对于树的问题大部分都是采用递归的方式进行求解的，这一题也是。不过在判断是否是平衡儿叉树的过程需要记录当前节点的深度用来判断左右节点高度的差值；另外利用一个state变量来保存当前遍历过程中得到树的状态，如果已经知道是非平衡二叉树直接返回即可。

代码如下：

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
class isBalanceTree1{
public:
    bool isBalanceTree(treeNode* root){
        bool cur_state = true;//记录当前的树的状态
        int level = 1; //树的高度从1开始算起
        getHeight(root, level, cur_state);
        return cur_state;
    }
    int getHeight(treeNode* root1, int level, bool& cur_state){
        if (root1 == NULL)
            return level;
            //如果节点是空，直接返回当前节点的深度
        int LH = getHeight(root1->left, level + 1, cur_state);
        //获取左子树的高度
        if (!cur_state)
            return level;
        // 如果已经知道是非平衡二叉树，直接返回即可。
        int RH = getHeight(root1->right, level + 1, cur_state);
        if (!cur_state)
            return level;
         //获取右子树的平衡状态
        if (RH - LH > 1 || LH - RH > 1)
            cur_state = false;
        // 如果深度差值超过1，平衡状态改变
        return LH >= RH ? LH : RH;
        // 获取子树中高度较深的那个节点
    }
};

题目描述2：

给定一棵树的头节点，要求判断这棵树是不是二叉搜索树。
具体的题目描述可以看LeetCode98.

解题思路:

因为是搜索二叉树，所以我们可以通过中序遍历的结果看其是否是升序的来判断是否是搜索二叉树。自然还有递归的解法待下次补上。

代码如下:

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
//是不是有效的二叉搜索树
/**
 * 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:
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        inOrder(root, vec);
        for (int i = 1; i < vec.size(); i++){
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
    void inOrder(TreeNode* head, vector<int>& vec){
        if (head == NULL) return;
        inOrder(head->left, vec);
        vec.push_back(head->val);
        inOrder(head->right, vec);
    }
};

题目描述3：

给定两棵树，要求判断这两棵树是否相等。
具体描述可以看LeetCode100.

代码如下:

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
/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return check(p, q);
    }
    bool check(TreeNode* t1, TreeNode* t2){
        if (t1 == NULL && t2 == NULL)
            return true;
        if ((t1 == NULL && t2 != NULL) || (t1 != NULL && t2 == NULL))
            return false;
        if (t1->val == t2->val)
            return check(t1->left, t2->left) && check(t1->right, t2->right);
        else 
            return false;
    }
};

题目描述4:

给定两棵树的头节点，要求判断这两棵树是否是互为镜像。
具体描述可以看LeetCode101.

代码如下:

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

发表于 | 分类于

Tree Contain Another Tree(判断一棵树是否包含另外一棵树的全部拓扑结构)

题目描述：

给定两棵树的根节点T1,T2;判断T1中是否包含了T2的全部拓扑结构。

解题思路：

主要的想法还是递归解决这个问题。首先我们在寻找两棵树是否相等过程中使用先序遍历的方法。我们可以先判断当前节点的相等关系，如果相等，则递归的判断左节点和右节点；如果不等我们可以判断当前节点的左子树和右子树和目标节点的包含关系。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class treeContains1{
public:
    bool treeContains(treeNode* root1, treeNode* root2){
        if (root2 == NULL)
            return true;
        if (root1 == NULL)
            return false;
        if (root1->val == root2->val)
            return treeContains(root1->left, root2->left) && treeContains(root1->right, root2->right);
           //如果相等的情况下，我们就各自向下遍历；
        if (root1->val != root2->val)
            return treeContains(root1->left, root2) || treeContains(root1->right, root2);
            // 如果不等的情况下，我们就判断当前节点的左节点和右节点和目标节点的依存关系。
    }
};

发表于 | 分类于

The Level In Tree(树中按层遍历相关的问题)

题目描述1：

给定一棵树的头结点head，实现按层遍历打印。

解题思路：

按层遍历的思路通常是借助于队列数据结构。我们先将节点入队，出队的时候将该节点的左右节点各自入队，当上一层的节点出队结束后，我们继续将刚刚入队的这一层节点出队，实现了按层遍历。我们可以使用两个队列分别来记录上一层和当前层的节点；也可以只用一个队的方法，每次记录当前入队的最后一个节点，下一层遍历的时候我们就只要出队到该节点即可。

代码如下：

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
class printByLevel1{ //利用两个队的方法
public:
    void printByLevel(treeNode* root){
        queue<treeNode*> q1;
        queue<treeNode*> q2; //定义两个队列
        queue<treeNode*> tmp;
        int level = 1;
        if (root == NULL)
            return;
        q1.push(root);//先将根节点入队
        while(!q1.empty()){
            cout << "Level" << level << ":";
            while(!q1.empty()){
                if (q1.front()->left != NULL){
                    q2.push(q1.front()->left);
                }
                if (q1.front()->right != NULL){
                    q2.push(q1.front()->right);
                }
                cout << q1.front()->val << " ";
                q1.pop();
            }//不断的将当前层的左右节点压入到另外一个队中
            tmp = q2;
            q2 = q1;
            q1 = tmp; //交换当前队和上一层队，对下一层节点遍历
            cout << endl;
        }
    }
};

解法2(只用一个队列的情况)

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
lass printByLevel2{
public:
    void printByLevel(treeNode* head){
        queue<treeNode*> q;
        treeNode* flag = head; //保存上一层的最后一个节点
        treeNode* next_flag = NULL; //保存当前层的最后一个节点
        q.push(head);
        while(!q.empty()){
            cout << q.front()->val;
            if (q.front()->left != NULL){
                q.push(q.front()->left);
                next_flag = q.front()->left; 
                //左节点入队，更新最后一个节点
            }
            if (q.front()->right != NULL){
                q.push(q.front()->right);
                next_flag = q.front()->right;
                //右节点入队，更新最后一个节点
            }
            if (q.front() == flag){
                cout << endl;
                flag = next_flag;
                //如果当前是最后一个节点，输出换行符，更新最后一个节点
            }
            q.pop();//出队头节点
        }
    }
};

题目描述2：

自底向上按层遍历树的每一层节点并返回结果。与上面题目类似，具体的题目描述可以看LeetCode107.

代码如下：

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
36
37
/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q1;
        q1.push(root);
        queue<TreeNode*>q2;
        queue<TreeNode*>tmp;
        while(!q1.empty()){
            vector<int> vec;
            while(!q1.empty()){
                vec.push_back(q1.front()->val);
                if (q1.front()->left) q2.push(q1.front()->left);
                if (q1.front()->right) q2.push(q1.front()->right);
                q1.pop();
            }
            res.push_back(vec);
            tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        reverse(res.begin(), res.end());
        //主要不同之处将遍历的结果逆序后返回即可
        return res;
    }
};

题目描述3：

定义树中的节点增加一个next节点，要求给定一棵树的头结点，要求每层的树的节点的next指针指向其同层右侧的指针。

例子：

详细的描述说明可以看leetcode上题目1，以及题目2.

解题思路：

初看题目可能会觉得思路上会有点卡壳，但是如果之前做过树的按层遍历的话，应该不难想到，我们可以一层一层的遍历树的节点，然后将每一层的树的节点连接起来就可以。

代码如下：

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
36
37
38
39
40
41
42
43
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        queue<TreeLinkNode*> q1;
        queue<TreeLinkNode*> q2;
        //定义两个队列用于保存上一层和当前层的树的节点
        q1.push(root);
        //先将树的头结点入队
        while(!q1.empty()){
            TreeLinkNode* pre = q1.front();
            q1.pop();
            if (pre->left) q2.push(pre->left);
            if (pre->right) q2.push(pre->right);
            //因为要将树的节点连接所以先将当前层的节点作为pre，剩下不断的往下遍历同层节点即可
            while(!q1.empty()){
                TreeLinkNode* next = q1.front();
                if (next->left) q2.push(next->left);
                if (next->right) q2.push(next->right);
                //每pop一个节点就将其左右节点入队，作为下一层的节点
                pre->next = next;
                //建立新的连接
                pre = next;
                //改变pre指针
                q1.pop();
            }
            pre->next = NULL;
            queue<TreeLinkNode*>tmp = q1;
            q1 = q2;
            q2 = tmp;
            //这步将下一层的数据保存到当前层的队列中，然后将下一层队列置空
        }
        
    }
};

题目描述4

类似用到树的按层遍历的性质的有，给定一棵树的头结点，要求输出从右侧看这棵树，从第一层到最后一层所看见的树的节点。其实这题的主要思路也是类似的，因为我们知道每层的节点后，我们只要将当前层的末尾节点保存到结果中就可以了。所以需要举一反三，利用之前的题目的解法可以很快的解答出。

例子:

这题也是leetcode上的题目，具体的题目描述可以看这边.

代码如下：

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
/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        //同样定义两个队列保存当前层和下一层的节点
        q1.push(root);
        while(!q1.empty()){
            res.push_back(q1.back()->val);
            //直接将当前层的末尾入队，即为最右侧的节点
            while(!q1.empty()){
                TreeNode* front = q1.front();
                if (front->left) q2.push(front->left);
                if (front->right) q2.push(front->right);
                q1.pop();
            }
            queue<TreeNode*> tmp = q1;
            q1 = q2;
            q2 = tmp;
            //更新当前层和下一层的数据
        }
    return res;
    }
};

题目描述5

给定一棵树的头结点，要求返回树的最左侧下方的那个节点。具体的描述可以看LeetCode513.解题思路是按层遍历，找到最后一层的最左侧节点返回即可。

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
/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> cur;
        queue<TreeNode*> next;
        vector<int> res;
        cur.push(root);
        while(!cur.empty()){
            res.push_back(cur.front()->val);
            while(!cur.empty()){
                TreeNode* front = cur.front();
                cur.pop();
                if (front->left) next.push(front->left);
                if (front->right) next.push(front->right);
            }
            queue<TreeNode*> tmp = cur;
            cur = next;
            next = tmp;
        }
        return res[res.size() - 1];
        //保存每一层的最左侧，返回最后一层的那个节点即可。
    }
};

题目描述6

给定一棵树的头结点，要求我们按照Z字型分层打印树的内容。
同样我们可以利用按层遍历树的方式，不同之处是需要加上一个direction标识用于判断当前层是从前往后还是从后往前答应。具体的题目描述可以看LeetCode103。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;w
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//按照锯齿状分层遍历树
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        
        deque<TreeNode*> q1;
        deque<TreeNode*> q2;
        deque<TreeNode*> tmp;
        bool direction = true;
        q1.push_back(root);
        while(!q1.empty()){
            vector<int> vec;
            while(!q1.empty() && direction){
                vec.push_back(q1.front()->val);
                if (q1.front()->left){
                    q2.push_front(q1.front()->left);
                }
                if (q1.front()->right){
                    q2.push_front(q1.front()->right);
                }
                q1.pop_front();
            }
            while(!q1.empty() && !direction){
                vec.push_back(q1.front()->val);
                if (q1.front()->right) q2.push_front(q1.front()->right);
                if (q1.front()->left) q2.push_front(q1.front()->left);
                q1.pop_front();
            }
            res.push_back(vec);
            direction = !direction;
            //每次遍历结束后都改变一下遍历的方向即可
            tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        return res;
        
        
    }
};

发表于 | 分类于

Serialization Of Tree(树的序列化和反序列化)

题目描述：

二叉树被记录文件的过程称为二叉树的序列化。通过文件来重建二叉树的过程称为二叉树的反序列化。给定一棵树的头结点head，设计一种二叉树序列化和反序列化的方案。

例子：

我们用！放在遍历结果的后面表示当前节点的结束，用#！表示当前节点为空结束。这样通过先序遍历一棵树得到的结果为：12!3!#!#!#!.

解题思路：

所以我们可以利用树的先序遍历来得到一棵树的序列化结果。在遍历每个节点后加上!,在每个根节点后面加上#!.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class serialByPre1{
public:
    string serialByPre(treeNode* root){
        string res = "";
        if (root == NULL)
            return "#!";
        res = to_string(root->val) + "!";
        res = res + serialByPre(root->left);
        res = res + serialByPre(root->right);
        return res;
    }
};

解题思路2：

对于树我们也可以使用按层遍历的方法得到其序列化的结果。使用的规则和上诉的一致，我们在节点结束后加上!,在空节点上加上#!.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class serialByLevel1{
public:
    string serialByLevel(treeNode* root){
        if (root == NULL)
            return NULL;
        string result = "";
        queue<treeNode*> q;
        stack<treeNode*> stk;//按层遍历利用两个栈来实现
        q.push(root);
        while(!q.empty()){
            cout <<  q.front()->val << endl;
            if (q.front()->left != NULL){
            		result += "#!";
                q.push(q.front()->left);
                }
            if (q.front()->right != NULL)
                q.push(q.front()->right);
            q.pop();
        }
    }
};

解题思路3

对于反序列化而言，我们首先要将拿到的字符串根据!隔开，分隔出每个节点的数值。因为原始数据是根据先序遍历得到的，所以假设在分隔后得到的字符串数组是[“12”,”3”,”#”,”#”,”#”].我们首先取出第一个字符串，开辟空间新建节点，用剩下的数据作为其左子树；取出第二个节点3生成节点，用剩下的作为左子树，发现是空节点，所以用剩下的构建右子树依旧是空节点；所以用[“#”,”#”]构建12节点的右子树。

代码如下：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class reconBySerialString1 {
public:
    queue<string> splitStrByDelimiter(string str) {
        queue<string> p;
        int start = 0;
        int distance = 0;
        string tmp = "";
        while (start < str.size()) {
            distance = str.substr(start, 11).find('!');
            tmp = str.substr(start, 11).substr(0, distance);
            p.push(tmp);
            start = start + distance + 1;
        }
        return p;
    }
    treeNode* reconBySerialString(queue<string> p){
        if (p.empty())
            return NULL;
        queue<treeNode*> q1;
        treeNode* head = new treeNode(stoi(p.front()));
        treeNode* result = head;
        q1.push(head);
        p.pop();
        while(!p.empty()){
            if (p.front() != "#"){
                treeNode* left = new treeNode(stoi(p.front()));
                q1.push(left);
                p.pop();
                head->left = left;
            }
            else{
                p.pop();
                head->left = NULL;
            }
            if (p.front() != "#"){
                treeNode* right = new treeNode(stoi(p.front()));
                p.pop();
                q1.push(right);
                head->right = right;
            }
            else{
                p.pop();
                head->right = NULL;
            }
            q1.pop();
            head = q1.front();
        }
        return result;
    }
};

发表于 | 分类于

Traverse Tree(遍历树的三种方法)

题目描述：

给定一棵树的头结点；给出先序遍历、中序遍历和后序遍历树的结果。

例子：

先序遍历是先遍历根节点，然后左节点，最后右节点；中序遍历是先遍历左节点，然后根节点最后右节点；后序遍历是最后遍历根节点。先序中序后序是以根节点为标准。

解题思路：

树的遍历主要是利用递归的方式进行查找。

代码如下：

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 printTree{
public:
    void preOrder(treeNode* root){
        if (root == NULL)
            return;
        std :: cout << root->val << std :: endl;//先根遍历
        preOrder(root->left);
        preOrder(root->right);
    }
    void inOrder(treeNode* root){
        if (root == NULL)
            return;
        inOrder(root->left);
        std :: cout << root->val << std :: endl; //中序遍历
        inOrder(root->right);
    }
    void postOrder(treeNode* root){
        if (root == NULL)
            return;
        postOrder(root->left);
        postOrder(root->right);
        std :: cout << root->val << std :: endl;//后序遍历
    }
};

解题思路2：

当然我们也可以使用非递归的方式对树进行遍历；主要的思路是在于将节点入栈后，根据不同的将左节点和右节点的压栈方式能够得到不同的遍历结果。

对于先根遍历而言，我们将某节点出栈后，先将该节点的右节点入栈，然后左节点入栈；对于中序遍历而言，我们是不断将最左侧的节点入栈，然后在弹出某节点后，将该节点的右侧节点入栈即可实现中序遍历；对于后序遍历而言我们利用了2个栈的方式，首先将根节点放入栈1，每次弹出的节点都放入栈2，并且将弹出节点的左侧和右侧节点压入栈1；不断进行直到栈1为空即可。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class printTreeUnrecur{
public:
    void preOrder(treeNode* root){
        if (root == NULL)
            return;
        std::stack<treeNode*> stk;
        stk.push(root);
        treeNode* tmp;
        while(!stk.empty()){
            if (stk.top() != NULL){
                tmp = stk.top();
                cout << tmp->val << endl;
                stk.pop(); //先打印出栈节点
                stk.push(tmp->right);
                stk.push(tmp->left);//先压入右侧节点在压入左侧节点
            }
            else{
                stk.pop();
            }
        }
    }
    void inOrder(treeNode* root){
        if (root == NULL)
            return;
        stack<treeNode*> stk;
        treeNode* tmp;
        while(root != NULL || !stk.empty()){
            if (root != NULL){
                stk.push(root);
                root = root->left;//先不断将左侧节点压栈
            }else{
                tmp = stk.top();
                cout << tmp->val << endl;//打印出栈的节点
                stk.pop();
                root = tmp->right; //遍历出栈节点的右侧节点
            }
        }
    }
    void postOrder(treeNode* root){
        if (root == NULL)
            return;
        std::stack<treeNode*> stk1;
        std::stack<treeNode*> stk2;
        stk1.push(root);
        treeNode* tmp;
        while(!stk1.empty()){
            tmp = stk1.top();
            stk1.pop();
            stk2.push(tmp); //出栈压入栈2中
            if (tmp->left != NULL)
                stk1.push(tmp->left);
            if (tmp->right != NULL)
                stk1.push(tmp->right);
                //将出栈节点的左侧和右侧节点压入栈1
        }
        while(!stk2.empty()){
            tmp = stk2.top();
            cout << tmp->val << endl;
            stk2.pop();//打印栈2中的数据即为遍历结果
        }
    }
};