Tree Special I

发表于 | 分类于

Tree Specail I

题目描述：

关于树的题目非常丰富，也具有一定的挑战性。所以在这边做一下小小的总结。主要是利用题目在总结一些在树题目中常见的思路和方法。
首先是给定一棵的头节点，判断这棵树是不是平衡二叉树。关于平衡二叉树，我们需要的主要是关于树的高度，任意节点的左右节点的深度差值不超过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
/**
 * 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 isBalanced(TreeNode* root) {
        if (!root) return true;
        //如果是空节点认为是平横的
        int left = height(root->left);
        //找到左子树的深度
        int right = height(root->right);
        //找到右节点的深度
        if (left - right > 1 || right - left > 1){
            return false;
            //差值超过1的情况
        }
        else{
            return isBalanced(root->left) && isBalanced(root->right);
            //不然就递归的判断左右节点的平衡性
        }
        
        
    }
    int height(TreeNode* head){
        if (!head) return 0;
        //空节点的情况返回深度为0
        int left = height(head->left) + 1;
        int right = height(head->right) + 1;
        //找到左右节点的深度
        return (left > right) ? left : right;
        //返回其中较大的作为深度返回
    }
};

题目描述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
/**
 * 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 minDepth(TreeNode* root) {
        if (!root) return 0;
        //如果是空节点返回0
        if (!root->left && !root->right) return 1;
        //如果只有一个根节点，返回1
        if (!root->left) return min(root->right) + 1;
        //如果是左节点为空的情况，我们直接找到右节点的最小深度即可
        if (!root->right) return min(root->left) + 1;
        //如果是右节点为空的情况下，我们直接找到左节点的最小深度
        return min(root);
        //不然我们就直接返回根节点的最小深度
        
    }
    int min(TreeNode* root) {
        if (!root->left && !root->right) return 1;
        //如果是叶节点的情况，返回高度为1
        int left = (root->left) ? (min(root->left) + 1) : INT_MAX; 
        //判断左节点的深度，其中如果是空的情况下，我们设定为INT_MAX,这样在返回的时候我们就不会返回这类节点了。
        int right = (root->right) ? (min(root->right) + 1): INT_MAX;
        return left > right ?  right : left;
        //返回其中较小的深度
        
    }
    
};

题目描述3：

另外一种在树中常见的题目是：我们需要根据树的先序遍历、中序遍历和后序遍历重构二叉树。就以用先序遍历和中序遍历来重构二叉树为例。假设一棵树的先序遍历是[1,2,4,5,3,6,7],中序遍历是[4,2,5,1,6,3,7],要求根据这个结果重建二叉树。

解题思路：

我们根据先序遍历和中序遍历的定义可以判断根节点是1,并且左节点的集合是[4,2,5]，右节点的集合是[6,3,7]。根据左节点集合的长度我们可以知道对于的先序遍历的集合分别为[2,4,5]和[3,6,7]。这样我们就可以递归的分别根据[4,2,5]和[2,4,5]建立左子树；根据[6,3,7]和[3,6,7]来建立右子树。

代码如下：

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
**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        return generate(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* generate(vector<int>& preorder, vector<int>& inorder, int p_left, int p_right, int i_left, int i_right)
    //我们定义构建树的函数输入为先序遍历结果，中序遍历结果，当前构建子树的先序遍历在先序遍历结果的左右位置，子树中序遍历在中序遍历结果中的左右位置
    {
        if (p_left == p_right){
            return new TreeNode(preorder[p_left]);
            //如果左右位置相等，直接构建节点返回
        }
        if (p_left > p_right) return NULL;
        //如果左边大于右边，说明已经没有节点可以用于构建子树，返回空节点
        
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == preorder[p_left]) {
                next = i;
                break;
            }
        }
        //用next来记录先序遍历的最左边的数在中序遍历中出现的位置，这个数是子树的根节点
        int left_length = next - i_left;
        //计算当前左子树的长度
        TreeNode* root = new TreeNode(inorder[next]);
        //以当前节点构建根节点
        root->left = generate(preorder, inorder, p_left + 1, p_left + left_length, i_left, next - 1);
        //改变中序遍历和先序遍历中左右位置，递归构建左子树
        root->right = generate(preorder, inorder, p_left + left_length + 1, p_right, next + 1, i_right);
        //改变中序遍历和先序遍历中左右位置，递归构建左子树
        return root;
           
    }
};

类似的根据中序遍历和后序遍历来构建二叉树的代码如下：

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return NULL;
        return generate(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
        
    }
    TreeNode* generate(vector<int>& inorder, vector<int>& postorder, int i_left, int i_right, int p_left, int p_right){
        if (i_left == i_right){
            return new TreeNode(inorder[i_left]);
        }
        if(i_left > i_right){
            return NULL;
        }
        int next = 0;
        for (int i = i_left; i <= i_right; i++){
            if (inorder[i] == postorder[p_right]){
                next = i;
                break;
            }
        }
        int length = i_right - next;
        TreeNode* root = new TreeNode(inorder[next]);
        root->left = generate(inorder, postorder, i_left, next - 1, p_left, p_right - length - 1);
        root->right = generate(inorder, postorder, next + 1, i_right, p_right - length, p_right - 1);
        return root;
    }
};