【遍历二叉树】10判断二叉树是否平衡【Balanced Binary 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
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

#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include "BinaryTree.h"

using namespace std;


/**
 * Definition for binary tree
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
bool balance(TreeNode *root, int &depth)
{
    if(root == NULL)
    {
        depth = 0;
        return true;
    }
    int leftdepth = 0;
    bool left = balance(root->left, leftdepth);

    int rightdepth = 0;
    bool right = balance(root->right, rightdepth);

    depth = leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
    int gap = leftdepth - rightdepth;

    return left && right && (-1 <= gap && gap <= 1);
}

bool isBalanced(TreeNode *root)
{

    int depth = 0;
    return balance(root, depth);
}



// 树中结点含有分叉，
//                  6
//              /       \
//             7         2
//           /   \
//          1     4
//               / \
//              3   5
int main()
{
    TreeNode *pNodeA1 = CreateBinaryTreeNode(6);
    TreeNode *pNodeA2 = CreateBinaryTreeNode(7);
    TreeNode *pNodeA3 = CreateBinaryTreeNode(2);
    TreeNode *pNodeA4 = CreateBinaryTreeNode(1);
    TreeNode *pNodeA5 = CreateBinaryTreeNode(4);
    TreeNode *pNodeA6 = CreateBinaryTreeNode(3);
    TreeNode *pNodeA7 = CreateBinaryTreeNode(5);

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);


    // 树中结点含有分叉，
    //                  1
    //              /       \
    //             2         2
    //           /   \       / \
    //          3     4     4   3

    TreeNode *pNodeB1 = CreateBinaryTreeNode(1);
    TreeNode *pNodeB2 = CreateBinaryTreeNode(2);
    TreeNode *pNodeB3 = CreateBinaryTreeNode(2);
    TreeNode *pNodeB4 = CreateBinaryTreeNode(3);
    TreeNode *pNodeB5 = CreateBinaryTreeNode(4);
    TreeNode *pNodeB6 = CreateBinaryTreeNode(4);
    TreeNode *pNodeB7 = CreateBinaryTreeNode(3);

    ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3);
    ConnectTreeNodes(pNodeB2, pNodeB4, pNodeB5);
    ConnectTreeNodes(pNodeB3, pNodeB6, pNodeB7);



    bool ans = isBalanced(pNodeA1);

    if (ans == true)
    {
        cout << "Balanced!" << endl;
    }
    else
    {
        cout << "Not Balanced!" << endl;
    }

    bool ans1 = isBalanced(pNodeB1);

    if (ans1 == true)
    {
        cout << "Balanced!" << endl;
    }
    else
    {
        cout << "Not Balanced!" << endl;
    }
    DestroyTree(pNodeA1);
    DestroyTree(pNodeB1);
    return 0;
}