剑指offer-平衡二叉树

平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例

给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。

思路

后续遍历+剪枝

对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则“剪枝”，直接向上返回

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isBalanced(root) {
    return recur(root) !== -1;
}

function recur(root) {
    if (root === null) return 0;
    let left = recur(root.left);
    if (left === -1) return -1;
    let right = recur(root.right);
    if (right === -1) return -1;
    return Math.abs(left-right) < 2 ? Math.max(left, right) + 1 : -1;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

平衡二叉树

思路

代码

CATALOG

FEATURED TAGS

FRIENDS