Point2OfferCode/55_2_Balance_Tree.cpp at master · slientreed/Point2OfferCode · GitHub

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

//
//  Created by mark on 2019/7/25.
//  Copyright © 2019年 mark. All rights reserved.
//

/*
 说明：
 1. 问题：55_2. 判断一个树是不是平衡二叉树
 2. 思路：1. 由上个题，递归左右子树深度，判断每个节点是否平衡。 （会出现大量重复遍历，效率低）
         2. 后序递归遍历树，每次遍历时保存它的深度，就可以一边遍历一遍判断了。不用出现大量重复。

 */

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <assert.h>

#include <cstdio>
#include <fstream>
#include <map>
#include <set>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};


int TreeDepth(TreeNode* root);
// 方法1.不断调用计算树深函数，判断每个节点是不是平衡树
bool isBalance(TreeNode* root)
{
    if(root == nullptr)
        return true;

    int left = TreeDepth(root->left);
    int right = TreeDepth(root->right);
    if(abs(left - right) > 1)
        return false;

    return isBalance(root->left) && isBalance(root->right);
}

// 方法2，后序遍历，每次遍历一个节点记录它的深度
bool isBalance2(TreeNode* root, int* depth)
{
    if(root == nullptr)
    {
        *depth = 0;
        return true;
    }

    int left_depth, right_depth;
    // 后序遍历
    bool left = isBalance2(root->left, &left_depth);       // 先遍历左子树
    bool right = isBalance2(root->right, &right_depth);    // 再遍历右子树

    if(left && right)                        // 遍历根节点，且记录当前层数
    {
        if(abs(left_depth - right_depth) <= 1)
        {
            *depth = 1 + max(left_depth, right_depth);    // 记录每个每个节点的深度
            return true;
        }
    }
    return false;
}


// 计算每个子树的深度
int TreeDepth(TreeNode* root)
{
    if(root == nullptr)
        return 0;

    int left = TreeDepth(root->left);     // 递归左子树
    int right = TreeDepth(root->right);   // 递归右子树

    return (left > right) ? (left + 1) : (right + 1);       // 返回左右子树中较大值加1
}


//辅助函数 ------------------------------------------------------------------------------------------------------------------------

// 构建树节点
TreeNode* CreateTreeNode(int val)
{
    TreeNode* pNode = new TreeNode();
    pNode->val = val;
    pNode->left = nullptr;
    pNode->right = nullptr;

    return pNode;
}

// 连接树节点
void ConnectTreeNodes(TreeNode* pParent, TreeNode* pLeft, TreeNode* pRight)
{
    if(pParent != nullptr)
    {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}


int main()
{

    //            8
    //        6      10
    //       5 7
    //     12
    TreeNode* pNode8 = CreateTreeNode(8);
    TreeNode* pNode6 = CreateTreeNode(6);
    TreeNode* pNode10 = CreateTreeNode(10);
    TreeNode* pNode5 = CreateTreeNode(5);
    TreeNode* pNode7 = CreateTreeNode(7);
    //TreeNode* pNode9 = CreateTreeNode(9);
    //TreeNode* pNode11 = CreateTreeNode(11);
    TreeNode* pNode12 = CreateTreeNode(12);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, nullptr, nullptr);
    ConnectTreeNodes(pNode5, pNode12, nullptr);

    int depth = 0;
    if(isBalance2(pNode8, &depth))
        cout << "是平衡树" << endl;
    else
        cout << "不是平衡树" << endl;

    return 0;
}