二叉树 - 平衡二叉树

本文主要是介绍二叉树 - 平衡二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

110. 平衡二叉树

方法一：递归法

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
var isBalanced = function (root) {// 递归三部曲 + 后序遍历 左右中// 当前左子树右子树高度相差大于1就返回-1// 1. 确定递归函数参数以及返回值const getDepth = function (node) {// 2. 确定递归函数终止条件if (node === null) return 0;// 3. 确定单层递归逻辑let leftDepth = getDepth(node.left);  // 左子树高度// 当判定左子树不为平衡二叉树时，即可直接返回-1if (leftDepth === -1) return -1;let rightDepth = getDepth(node.right);  // 右子树高度// 当判定右子树不为平衡二叉树时，即可直接返回-1if (rightDepth === -1) return -1;if (Math.abs(leftDepth - rightDepth) > 1) {return -1;} else {return 1 + Math.max(leftDepth, rightDepth);}}return !(getDepth(root) === -1);
};

方法二：迭代法

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
var isBalanced = function (root) {if (root === null) return true;let queue = [root];while (queue.length) {let node = queue[queue.length - 1];  // 取出栈顶queue.pop();if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {return false;}node.right && queue.push(node.right);node.left && queue.push(node.left);}return true;
};// 获取当前节点的高度
var getHeight = function (curNode) {let queue = [];if (curNode !== null) queue.push(curNode);  // 压入当前元素let depth = 0, res = 0;while (queue.length) {let node = queue[queue.length - 1];  // 取出栈顶if (node !== null) {queue.pop();queue.push(node);  // 中queue.push(null);depth++;node.right && queue.push(node.right);  // 右node.left && queue.push(node.left);  // 左} else {queue.pop();node = queue[queue.length - 1];queue.pop();depth--;}res = res > depth ? res : depth;}return res;
}

这篇关于二叉树 - 平衡二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---