LeetCode 110.平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回fasle
二叉树的深度和高度:
深度是自顶向下,高度是自下往上。
思路:
本题的思路是对高度或深度的计算,深度用前序遍历中左右。 高度用后序遍历,左右中。
对左右孩子节点的深度和高度进行比较,如果高度差大于1时,直接return false
class Solution { /** * 递归法 */ public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = getHeight(root.left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root.right); if (rightHeight == -1) { return -1; } // 左右子树高度差大于1,return -1表示已经不是平衡树了 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } } class Solution { /** * 迭代法,效率较低,计算高度时会重复遍历 * 时间复杂度:O(n^2) */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while (root!= null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } TreeNode inNode = stack.peek(); // 右结点为null或已经遍历过 if (inNode.right == null || inNode.right == pre) { // 比较左右子树的高度差,输出 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { return false; } stack.pop(); pre = inNode; root = null;// 当前结点下,没有要遍历的结点了 } else { root = inNode.right;// 右结点还没遍历,遍历右结点 } } return true; } /** * 层序遍历,求结点的高度 */ public int getHeight(TreeNode root) { if (root == null) { return 0; } Deque<TreeNode> deque = new LinkedList<>(); deque.offer(root); int depth = 0; while (!deque.isEmpty()) { int size = deque.size(); depth++; for (int i = 0; i < size; i++) { TreeNode poll = deque.poll(); if (poll.left != null) { deque.offer(poll.left); } if (poll.right != null) { deque.offer(poll.right); } } } return depth; } } class Solution { /** * 优化迭代法,针对暴力迭代法的getHeight方法做优化,利用TreeNode.val来保存当前结点的高度,这样就不会有重复遍历 * 获取高度算法时间复杂度可以降到O(1),总的时间复杂度降为O(n)。 * 时间复杂度:O(n) */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } TreeNode inNode = stack.peek(); // 右结点为null或已经遍历过 if (inNode.right == null || inNode.right == pre) { // 输出 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { return false; } stack.pop(); pre = inNode; root = null;// 当前结点下,没有要遍历的结点了 } else { root = inNode.right;// 右结点还没遍历,遍历右结点 } } return true; } /** * 求结点的高度 */ public int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = root.left != null ? root.left.val : 0; int rightHeight = root.right != null ? root.right.val : 0; int height = Math.max(leftHeight, rightHeight) + 1; root.val = height;// 用TreeNode.val来保存当前结点的高度 return height; } }
原文地址:http://www.cnblogs.com/dwj-ngu/p/16891110.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性