leetcode/src/Balanced_Binary_Tree.cpp at master · zyx4843/leetcode · 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
// Source : https://oj.leetcode.com/problems/balanced-binary-tree/
// Author : zheng yi xiong
// Date   : 2014-12-20

/**********************************************************************************
*
* Given a binary tree, determine if it is height-balanced.

* For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
*
**********************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
	int TreeDepth(TreeNode *pNode, bool &bBalanced)
	{
		if (!bBalanced)
		{
			return 0;
		}

		int left_depth = 0, right_depth = 0;
		if (NULL != pNode->left)
		{
			left_depth = TreeDepth(pNode->left, bBalanced);
		}

		if (NULL != pNode->right)
		{
			right_depth = TreeDepth(pNode->right, bBalanced);
		}

		if (bBalanced)
		{
			int div_depth = left_depth - right_depth;
			if ( 1 < div_depth || -1 > div_depth)
			{
				bBalanced = false;
			}
		}

		return left_depth > right_depth ? (left_depth + 1) : (right_depth + 1);
	}
public:
	bool isBalanced(TreeNode *root) {
		if (NULL == root)
		{
			return true;
		}
		bool bBalanced = true;
		int depth = TreeDepth(root, bBalanced);
		return bBalanced;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	TreeNode node1(5);
	TreeNode node2_1(4);
	TreeNode node2_2(8);
	TreeNode node3_1(11);
	//TreeNode node3_2(13);
	TreeNode node3_3(4);
	TreeNode node4_1(7);
	TreeNode node4_2(2);
	TreeNode node4_3(1);
	node1.left = &node2_1;
	node1.right = &node2_2;
	node2_1.left = &node3_1;
	//node2_2.left = &node3_2;
	node2_2.right = &node3_3;
	node3_1.left = &node4_1;
	node3_1.right = &node4_2;
	node3_3.right = &node4_3;

	Solution so;
	bool bBalanced = so.isBalanced(&node1);

	return 0;
}