文章目录104.二叉树的最大深度226. 翻转二叉树101.对称二叉树543. 二叉树的直径102.二叉树的层序遍历108. 将有序数组转换为二叉搜索树104.二叉树的最大深度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; * } * } */classSolution{publicintmaxDepth(TreeNoderoot){if(rootnull)return0;intleftmaxDepth(root.left);intrightmaxDepth(root.right);returnMath.max(left,right)1;}}226. 翻转二叉树226. 翻转二叉树先递归到底再交换/** * 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; * } * } */classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(rootnull)returnnull;invertTree(root.left);invertTree(root.right);TreeNodetemproot.left;root.leftroot.right;root.righttemp;returnroot;}}101.对称二叉树101. 对称二叉树将整棵树的对称问题转化为判断“左子树”和“右子树”是否互为镜像。通过check函数每次递归都严格比较两个节点的值是否相等然后让左节点的“左孩子”与右节点的“右孩子”对比同时让左节点的“右孩子”与右节点的“左孩子”对比即交叉比较一路递归到底只要所有交叉对应的节点都匹配整棵树就是对称的/** * 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; * } * } */classSolution{publicbooleanisSymmetric(TreeNoderoot){returncheck(root.left,root.right);}publicbooleancheck(TreeNodeleft,TreeNoderight){//两边都为空 对称if(leftnullrightnull)returntrue;//只有一边为空或者值不同 不对称if(leftnull||rightnull||left.val!right.val)returnfalse;//继续向下交叉比较returncheck(left.left,right.right)check(left.right,right.left);}}543. 二叉树的直径543. 二叉树的直径遍历二叉树在计算最大深度的同时顺带把直径算出来在当前节点拐点的直径长度 左子树的最大深度 右子树的最大深度返回给父节点的是当前子树的最大深度 max(左子树的最大深度右子树的最大深度)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; * } * } */classSolution{privateintres0;publicintdiameterOfBinaryTree(TreeNoderoot){maxDepth(root);returnres;}publicintmaxDepth(TreeNoderoot){if(rootnull)return0;intleftmaxDepth(root.left);intrightmaxDepth(root.right);resMath.max(res,leftright);returnMath.max(left,right)1;}}102.二叉树的层序遍历102. 二叉树的层序遍历BFScur数组存当前正在遍历的节点nxt数组存被遍历节点的左右子节点vals数组存部分答案遍历cur把左右子节点记录到nxt中同时把节点值记录到数组vals中遍历结束后把vals加到答案里遍历结束把cur替换成nxt开始下一轮循环cur不为空就证明还没遍历完/** * 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; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull)returnList.of();ListListIntegeransnewArrayList();ListTreeNodecurList.of(root);while(!cur.isEmpty()){ListTreeNodenxtnewArrayList();ListIntegervalsnewArrayList(cur.size());for(TreeNodenode:cur){vals.add(node.val);if(node.left!null)nxt.add(node.left);if(node.right!null)nxt.add(node.right);}curnxt;ans.add(vals);}returnans;}}优化一下把cur数组和nxt数组用一个队列替代/** * 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; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull)returnList.of();ListListIntegeransnewArrayList();QueueTreeNodeqnewArrayDeque();q.add(root);while(!q.isEmpty()){intnq.size();ListIntegervalsnewArrayList(n);while(n0){TreeNodenodeq.poll();vals.add(node.val);if(node.left!null)q.add(node.left);if(node.right!null)q.add(node.right);n--;}ans.add(vals);}returnans;}}108. 将有序数组转换为二叉搜索树108. 将有序数组转换为二叉搜索树平衡二叉搜索树每个节点的左子树和右子树高度相差不超过1由于给定的数组是严格升序的要构建一棵高度平衡的二叉搜索树BST关键在于每次都选取当前区间的中间元素作为根节点这样能保证左右子树的节点数量尽可能相等随后以中间元素为界将数组一分为二递归地对左半区间构建左子树、对右半区间构建右子树直到区间越界left right时返回null作为递归出口最终自底向上拼接出一棵完美的平衡二叉搜索树。/** * 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; * } * } */classSolution{publicTreeNodesortedArrayToBST(int[]nums){returnbuild(nums,0,nums.length-1);}publicTreeNodebuild(int[]nums,intleft,intright){if(leftright)returnnull;intmid(leftright)/2;TreeNoderootnewTreeNode(nums[mid]);root.leftbuild(nums,left,mid-1);root.rightbuild(nums,mid1,right);returnroot;}}