南阳网站运营招聘信息,app定制软件开发哪家好,做网站点击软件,wordpress 猪八戒110.平衡二叉树 方法一#xff1a;自顶向下递归
对于当前遍历到的节点#xff0c;首先计算左右子树的高度#xff0c;如果左右子树的高度差是否不超过 111#xff0c;再分别递归地遍历左右子节点#xff0c;并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。…110.平衡二叉树 方法一自顶向下递归
对于当前遍历到的节点首先计算左右子树的高度如果左右子树的高度差是否不超过 111再分别递归地遍历左右子节点并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {if(root null){return true;}else{return Math.abs(height(root.left)- height(root.right)) 1 isBalanced(root.left) isBalanced(root.right);}}public int height(TreeNode root){if(root null){return 0;}else{return Math.max(height(root.left),height(root.right)) 1;}}
}方法二自底向上递归
对于当前遍历到的节点先递归地判断其左右子树是否平衡再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的则返回其高度高度一定是非负整数否则返回 −1。如果存在一棵子树不平衡则整个二叉树一定不平衡。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return height(root) 0;}public int height(TreeNode root){if(root null){return 0;}int left height(root.left);int right height(root.right);if(left -1 || right -1 || Math.abs(left - right) 1){return -1;}else{return Math.max(left,right) 1;}}
}
