【力扣hot100】二叉树专题-平芜编程栈

文章目录

- - 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(root==null)return0;intleft=maxDepth(root.left);intright=maxDepth(root.right);returnMath.max(left,right)+1;}}

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(root==null)returnnull;invertTree(root.left);invertTree(root.right);TreeNodetemp=root.left;root.left=root.right;root.right=temp;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(left==null&&right==null)returntrue;//只有一边为空或者值不同 不对称if(left==null||right==null||left.val!=right.val)returnfalse;//继续向下交叉比较returncheck(left.left,right.right)&&check(left.right,right.left);}}

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{privateintres=0;publicintdiameterOfBinaryTree(TreeNoderoot){maxDepth(root);returnres;}publicintmaxDepth(TreeNoderoot){if(root==null)return0;intleft=maxDepth(root.left);intright=maxDepth(root.right);res=Math.max(res,left+right);returnMath.max(left,right)+1;}}

102.二叉树的层序遍历

102. 二叉树的层序遍历

BFS

cur数组存当前正在遍历的节点
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{publicList<List<Integer>>levelOrder(TreeNoderoot){if(root==null)returnList.of();List<List<Integer>>ans=newArrayList<>();List<TreeNode>cur=List.of(root);while(!cur.isEmpty()){List<TreeNode>nxt=newArrayList<>();List<Integer>vals=newArrayList<>(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);}cur=nxt;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{publicList<List<Integer>>levelOrder(TreeNoderoot){if(root==null)returnList.of();List<List<Integer>>ans=newArrayList<>();Queue<TreeNode>q=newArrayDeque<>();q.add(root);while(!q.isEmpty()){intn=q.size();List<Integer>vals=newArrayList<>(n);while(n>0){TreeNodenode=q.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. 将有序数组转换为二叉搜索树

平衡二叉搜索树：每个节点的左子树和右子树高度相差不超过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(left>right)returnnull;intmid=(left+right)/2;TreeNoderoot=newTreeNode(nums[mid]);root.left=build(nums,left,mid-1);root.right=build(nums,mid+1,right);returnroot;}}