The Type Of Tree

发表于 | 分类于

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