[LeetCode] 110. Balanced Binary Tree

轉自LeetCode

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.

<Solution>

這題是要檢查 binary tree 是否是 height-balanced

根據題目定義，如果一個 binary tree 是 height-balanced，則每個子樹也都會是 height-balanced

因此，使用 recursive 的解法來解

• 以當下的 node 為 root，記算左右子樹的高度，看看是否差距小於 1

• 如果差距小於1，再分別檢查以 left node 為 root 的子樹，和以 right node 為 root 的子樹是否也符合條件

code 如下 (參考資料)

	/**
	* 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 leftDepth = height(root->left);
	int rightDepth = height(root->right);
	//> recursive check
	return (abs(leftDepth - rightDepth) <= 1) && isBalanced(root->left) && isBalanced(root->right);
	}
	int height(TreeNode *root) {
	if(!root) {
	return 0;
	}
	return max(height(root->left), height(root->right)) + 1;
	}
	};

view raw heightBalancedBinaryTree_1.cpp hosted with ❤ by GitHub

不過上面這個解法的平均時間複雜度是O(NlogN)

每個 root 都要往下歷遍每個node來找高度，總共會做 lnN 次

所以可以用 DFS 改良一下寫法，是一種 bottom-up 的想法

• 先用 DFS 走到 leaf node

• 檢查是否是 height-balanced，是的話，回傳高度資訊；不是的話，回傳 -1

• 最後在 root 的地方，確認 DFS 的結果是不是 -1 即可

code 如下(參考資料)
c++

	/**
	* 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) {
	return (dfsHeight(root) != -1);
	}
	int dfsHeight(TreeNode *root) {
	if(!root) {
	return 0;
	}
	int leftHeight = dfsHeight(root->left);
	if(leftHeight == -1) {
	return -1;
	}
	int rightHeight = dfsHeight(root->right);
	if(rightHeight == -1) {
	return -1;
	}
	if(abs(leftHeight - rightHeight) > 1) {
	return -1;
	}
	else {
	return max(leftHeight, rightHeight) + 1;
	}
	}
	};

view raw heightBalancedBinaryTree_2.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun isBalanced(root: TreeNode?): Boolean {
	return check(root) != -1
	}
	fun check(node: TreeNode?): Int {
	if(node == null) {
	return 0
	}
	val leftHeight = check(node!!.left)
	if(leftHeight == -1) {
	return -1
	}
	val rightHeight = check(node!!.right)
	if(rightHeight == -1) {
	return -1
	}
	return if(Math.abs(leftHeight - rightHeight) > 1) {
	-1
	} else {
	Math.max(leftHeight, rightHeight) + 1
	}
	}
	}

view raw balanced_binary_tree.kt hosted with ❤ by GitHub