代码随想三刷二叉树篇2

101. 对称二叉树

题目

链接

代码

/*** 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 isSymmetric(TreeNode root) {if(root==null){return true;}   return traverse(root.left,root.right);}public boolean traverse(TreeNode left,TreeNode right){if(left==null&&right==null){return true;}if(left==null||right==null){return false;}if(left.val!=right.val){return false;}return traverse(left.left,right.right)&&traverse(left.right,right.left);}
}

104. 二叉树的最大深度

题目

链接

代码

/*** 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 int maxDepth(TreeNode root) {findDepth(root,1);return maxDepth;}int maxDepth = 0;public void findDepth(TreeNode root,int depth){if(root==null){return;}maxDepth = Math.max(maxDepth,depth);findDepth(root.left,depth+1);findDepth(root.right,depth+1);}
}

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 int minDepth(TreeNode root) {if(root==null){return 0;}traverse(root,1);return min;}   int min = Integer.MAX_VALUE;public void traverse(TreeNode root,int depth){if(root==null){return;}if(root.left==null&&root.right==null){min = Math.min(min,depth);}traverse(root.left,depth+1);traverse(root.right,depth+1);}
}

222. 完全二叉树的节点个数

题目

链接

代码

/*** 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 int countNodes(TreeNode root) {preOrder(root);return count;}int count = 0;public void preOrder(TreeNode root){if(root==null){return;}count++;preOrder(root.left);preOrder(root.right);}
}

110. 平衡二叉树

题目

链接

代码

/*** 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;}high(root);return isBalanced;}boolean isBalanced = true;public int high(TreeNode root){if(root==null){return 0;}if(root.left==null&&root.right==null){//叶子高为1return 1;}int left = high(root.left);int right = high(root.right);if(Math.abs(left-right)>1){isBalanced = false;}return Math.max(left,right)+1;}
}

257. 二叉树的所有路径

题目

链接

代码

/*** 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 List<String> binaryTreePaths(TreeNode root) {preOrder(root);return result;}List<String> result = new ArrayList();List<Integer> list = new ArrayList();public void preOrder(TreeNode root){if(root==null){return;}list.add(root.val);if(root.left==null&&root.right==null){StringBuilder sb = new StringBuilder();for(int i =0;i<list.size();i++){if(i==0){sb.append(list.get(i));}else{sb.append("->"+list.get(i));}}result.add(sb.toString());}if(root.left!=null){preOrder(root.left);list.remove(list.size()-1);}if(root.right!=null){preOrder(root.right);list.remove(list.size()-1);}}
}