赞
踩
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)
{
return 0;
}
else
{
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return Math.max(left,right)+1;
}
}
}
110.平衡二叉树判断
class Solution { public boolean isBalanced(TreeNode root) { if (height(root)==-1) { return false; } else { return true; } } public int height(TreeNode root) { if(root==null) { return 0; } else { int leftheight=height(root.left); int rightheight=height(root.right); if (Math.abs(leftheight-rightheight)>1||leftheight==-1||rightheight==-1) { return -1; } else { return Math.max(leftheight,rightheight)+1; } } } }
class Solution { int maxpath=0; public int diameterOfBinaryTree(TreeNode root) { diametersubtree(root); return maxpath; } public int diametersubtree(TreeNode root) { if(root==null) { return 0; } else { int left=diametersubtree(root.left); int right=diametersubtree(root.right); if((left+right)>maxpath) maxpath=left+right; return Math.max(left,right)+1; } } }
class Solution { public int pathSum(TreeNode root, int sum) { if(root==null) { return 0; } else { return diametersubtree(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum); } } public int diametersubtree(TreeNode root,int sum) { if(root==null) { return 0; } else { // int count=0; // if(root.val==sum) // { // count=1; // } int count=root.val==sum?1:0; count+=diametersubtree(root.left,sum-root.val); count+=diametersubtree(root.right,sum-root.val); return count; } } }
注:543和437的区别:
class Solution { int maxpath=Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { diametersubtree(root); return maxpath; } public int diametersubtree(TreeNode root) { if(root==null) { return 0; } else { int left=Math.max(diametersubtree(root.left),0); int right=Math.max(diametersubtree(root.right),0); if((left+right+root.val)>maxpath) maxpath=left+right+root.val; return Math.max(left,right)+root.val; } } }
class Solution { public boolean isSymmetric(TreeNode root) { if(root==null) { return true; } return helper(root.left,root.right); } private boolean helper(TreeNode t1,TreeNode t2) { if(t1==null&&t2==null) { return true; } if(t1==null||t2==null) { return false; } if(t1.val!=t2.val) { return false; } return helper(t1.left,t2.right)&&helper(t1.right,t2.left); } }
class Solution { public boolean isValidBST(TreeNode root) { return helper(root,null,null); } public boolean helper(TreeNode root,TreeNode min,TreeNode max) { if(root==null) { return true; } else { if(min!=null&&root.val<=min.val) { return false; } if(max!=null&&root.val>=max.val) { return false; } else { return helper(root.left,min,root) && helper (root.right,root,max); } } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。