阿里云9元做网站,湘潭培训网站建设,wordpress 淘宝客主题,互联网中厂有哪些公司#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 对称二叉树 1.1 判断对称二叉树实现思路 1.2 代码实现#xff1a;判断对称二叉树 2.0 二叉树的最大深度 2.1 使用递归实现获取二叉树的最大深度思路 2.2 代码实… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 对称二叉树 1.1 判断对称二叉树实现思路 1.2 代码实现判断对称二叉树 2.0 二叉树的最大深度 2.1 使用递归实现获取二叉树的最大深度思路 2.2 代码实现使用递归实现获取二叉树的最大深度 2.3 使用非递归实现获取二叉树的最大深度思路 2.4 代码实现使用非递归实现获取二叉树的最大深度 2.5 使用层序遍历实现获取二叉树的最大深度 2.6 代码实现使用层序遍历实现获取二叉树的最大深度 3.0 二叉树的最小深度 3.1 使用递归实现获取二叉树的最小深度思路 3.2 代码实现使用递归实现获取二叉树最小深度 3.3 使用层序遍历实现获取二叉树的最小深度思路 3.4 代码实现使用层序遍历实现获取二叉树的最小深度 4.0 翻转二叉树 4.1 使用实现递归翻转二叉树思路 4.2 代码实现使用递归翻转二叉树 5.0 二叉树经典解法的完整代码 1.0 对称二叉树 题目 给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出falseOJ链接 101. 对称二叉树 1.1 判断对称二叉树实现思路 假设该树的图 具体思路为如果当前节点的左子树的值等于当前节点的右子树时可以说目前为止还是对称的不能直接下结论因为不能保证之后的节点是否对称。比如当前节点的值为 1 它的左孩子的值为 2 它的右孩子的值为 2此时可以说暂时是对称的还需要接着向下判断。它的左孩子的左孩子的值为 3它的右孩子的右孩子为 3 同理现在还不能说明该树是否对称当递归到底的时候当前的节点的左右孩子都是 null 此时可以返回 true 不能足以证明该树对称因为单单只是判断完外侧的节点在外层回归的过程中需要判断内层的节点是否对称回归到节点值都为 2 的节点接着进行内层递归对于在外层判断完左孩子那么接下来需要判断右孩子同样对于在外层判断完右孩子那么接下来需要判断左孩子。如刚刚的外层结束递出之后开始回归到节点为 2 的节点对于左边的节点值为 2 的节点的右孩子与右边的节点值为 2 的节点的左孩子进行比较如果相同由于说明不了什么还得继续往下递出直到该节点的左右孩子都为 null 时可以返回 true 。最后返回到节点值为 1 的根节点中可以得到该树是对称。 在无论是外层递出还是内层递出 - 当左右孩子节点的值不相同的时候就说明了该树时不相等的直接返回 false - 遇到一个节点的左孩子不为 null 而右孩子为 null 时可以直接返回 false 不需要接着往后递出了。同理遇到一个节点的右孩子不为 null 而左孩子为 null 时直接返回 false - 当且仅当当该节点的左右孩子都为 null 时返回 true 1.2 代码实现判断对称二叉树 //判断对称二叉树public boolean isSymmetry(TreeNode root) {return isSymmetryRecursion(root.left,root.right);}private boolean isSymmetryRecursion(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 isSymmetryRecursion(left.left,right.right) isSymmetryRecursion(left.right,right.left);} 大体上的思路跟后序遍历二叉树一致。 2.0 二叉树的最大深度 题目 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7]
输出3 OJ链接 104. 二叉树的最大深度 2.1 使用递归实现获取二叉树的最大深度思路 具体思路为先从整体思路出发得到最大的深度无非就是比较左右子树的深度选取较大的值 1返回即可。当遇到的节点为 null 时返回 0 结束递出。比如节点值为 3 的节点它的左子树的深度为 1它的右子树的深度为 2 ,那么选取最大的值为 2 最后最大的值再加上 1 所以得出的该树的最大深度为 3 。 接下来具体分析每一个节点根节点值为 3 先获取左子树的深度沿着该方向递出直到遇到当前节点的左右孩子都为 null 时返回 0 所以值为 9 的节点目前返回上一个递归调用的值为 1 对于根节点的左子树的深度为 1 再获取右子树的深度沿着根节点的右子树递出这次遇到的节点的左右子树都不为 null 时对于当前值为 20 的节点来说需要获取该左右子树的最大的值先获取左子树的深度沿着该方式递出直到遇到的节点为 null 时返回 0节点值为 15 的节点的左右孩子都为 null 返回 0 1 所以对于节点 20 来说该左子树的深度为 1 接着继续来获取节点值为 20 的右子树的深度沿着该方式递出直到遇到的节点为 null 时返回 0节点值为 7 的左右孩子都为 null 返回 0 1。那么选取较大的值 1就是节点值为 20 的深度为 2 。相对与根节点来说已经得到了左右子树的深度了分别为 1 与 2 选取最大的值 2 再加 1 就是该树的最大深度为 3 。 2.2 代码实现使用递归实现获取二叉树的最大深度 //用递归方式求树的最大深度public int maximumDepthRecursion(TreeNode node) {if (node null) {return 0;}int l maximumDepth(node.left);int r maximumDepth(node.right);return Math.max(l,r) 1;} 大体上思路跟后序遍历思路大致相同。 2.3 使用非递归实现获取二叉树的最大深度思路 具体思路为在之前讲到使用非递归实现后序遍历的思路跟这里的思路大致一致。简单再讲一下思路根节点从左孩子开始出发在到下一个节点之前需要先把该节点压入栈中直到 node null 时不再继续下去按照原路返回。由于需要完成对右节点的操作后需要返回该节点所以不能直接把栈顶元素弹出先查找栈顶元素查看该右孩子是否为 null 或者已经完成对右孩子的相关操作之后这才能弹出栈顶元素。如果以上情况都不符合需要对右孩子进行处理。以上就是使用非递归实现后序循环那么结合该题求树的最大深度即什么时候栈的元素达到最大的时候这时候就是树的最大深度。 2.4 代码实现使用非递归实现获取二叉树的最大深度 //用非递归方式求树的最大深度public int maximumDepth(TreeNode root) {TreeNode curr root;LinkedListTreeNode stack new LinkedList();int max 0;TreeNode pop null;while (curr ! null || !stack.isEmpty()) {if (curr ! null) {stack.push(curr);curr curr.left;if (max stack.size()) {max stack.size();}} else {TreeNode peek stack.peek();if ( peek.right null || peek.right pop ) {pop stack.pop();}else {curr peek.right;}}}return max;} 当然这个时间复杂度比使用递归实现的要大效率不如使用递归的实现二叉树最大深度。 2.5 使用层序遍历实现获取二叉树的最大深度 先了解层序遍历顾名思义按照层级进行依次访问节点。将每个节点压入队列中按照先进先出的顺序依次访问队列中的节点。具体来说我们从根节点开始将根节点压入队列中然后依次从队列中取出节点将其左右子节点如果存在压入队列中。 需要准备队列来存储节点根据该数据结构的特性先进先出一开始先让根节点压入队列中接着从队列中弹出来如果弹出来的节点的左孩子不为 null 时将其压入队列中如果左孩子为 null 时不需要压入队列中同理如果弹出来节点的右孩子不为 null 时将其压入队列中。循环结束条件为当队列中的元素个数为 0 时退出循环。 再结合该题的逻辑该二叉树的最大深度就是树的层级数量。那么怎么才能得出 int depth 层级数量呢再嵌套一个内层循环每一层遍历结束之后depth 。内层循环的次数为当前的队列的元素的个数。 2.6 代码实现使用层序遍历实现获取二叉树的最大深度 //使用层序遍历求树的最大深度public int sequenceMaxDepth(TreeNode root) {if (root null) {return 0;}LinkedListTreeNode queue new LinkedList();queue.offer(root);int depth 0;while ( !queue.isEmpty()) {int size queue.size();for (int j 0; j size; j) {TreeNode tp queue.poll();if (tp.left ! null) {queue.offer(tp.left);}if (tp.right ! null) {queue.offer(tp.right);}//System.out.print(tp.val );}//System.out.println();depth;}return depth;} 3.0 二叉树的最小深度 题目 给定一个二叉树找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明叶子节点是指没有子节点的节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出2OJ链接 111. 二叉树的最小深度 二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数量。换句话说最小深度是从根节点到最近的叶子节点的路径长度。 3.1 使用递归实现获取二叉树的最小深度思路 具体思路为思路大体跟或去最大深度的思路差不太多当比较前节点的左右子树获取最小的值 1 则为当前节点的深度。获取最小深度相较于获取最大深度多了一个判断条件如果当前节点为 0 时不应该参与比较。 如图例该树的深度应该为 2 如果不加额外的条件来判断左右孩子节点是否为 null 时那么此时根节点的右孩子为 null 所以右子树为深度为 0 左孩子不为 null 接着递归下去直到 node null 为止从图可知该根节点的左子树的深度为 1因此用 1 与 0 来比较获取最小的值为 0 再加上 1 ,最后结果为 1 。很明显不符合要求。所以一定要加条件来判断查看该节点的左右孩子是否为 null 如果为 null 需要返回另一个节点 1 当作当前节点的深度。 3.2 代码实现使用递归实现获取二叉树最小深度 //使用递归求树的最小深度public int minDepth(TreeNode node) {if (node null) {return 0;}int l minDepth(node.left);int r minDepth(node.right);if (l 0) {return r 1;}if (r 0) {return l 1;}return Math.min(l,r) 1;} 3.3 使用层序遍历实现获取二叉树的最小深度思路 具体思路为当带一个遇到的叶子节点时当前的层数就是该树的最小深度。 3.4 代码实现使用层序遍历实现获取二叉树的最小深度 //使用层序遍历求得树的最小深度public int sequenceMinDepth(TreeNode root) {LinkedListTreeNode queue new LinkedList();queue.offer(root);int depth 0;while (!queue.isEmpty()) {depth;int size queue.size();for (int i 0; i size ; i) {TreeNode poll queue.poll();if (poll.right null poll.left null) {return depth;}if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}}}return depth;} 4.0 翻转二叉树 题目 给定一棵二叉树的根节点 root请左右翻转这棵二叉树并返回其根节点。 示例 1 输入root [5,7,9,8,3,2,4]
输出[5,9,7,4,2,3,8] OJ链接 LCR 144. 翻转二叉树 4.1 使用实现递归翻转二叉树思路 具体思路为从整体来看将当前节点的左右节点进行翻转每一个节点都是如此递归结束条件为 node null 时结束递出。回归到每一个节点的右子树进行翻转。 4.2 代码实现使用递归翻转二叉树 //翻转二叉树public void rollbackRecursion(TreeNode node) {if (node null) {return;}TreeNode temp node.left;node.left node.right;node.right temp;rollbackRecursion(node.left);rollbackRecursion(node.right);}5.0 二叉树经典解法的完整代码
回顾本章代码进一步巩固 import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class TreeNode {private TreeNode left;private int val;private TreeNode right;public TreeNode(int val) {this.val val;}public TreeNode(TreeNode left, int val, TreeNode right) {this.left left;this.val val;this.right right;}//递归实现前序遍历public void prevRecursion(TreeNode node) {if (node null) {return;}System.out.print(node.val );prevRecursion(node.left);prevRecursion(node.right);}//递归实现中序遍历public void midRecursion(TreeNode node) {if (node null) {return;}midRecursion(node.left);System.out.print(node.val );midRecursion(node.right);}//递归实现后序遍历public void postRecursion(TreeNode node) {if (node null) {return;}postRecursion(node.left);postRecursion(node.right);System.out.print(node.val );}//非递归实现前序遍历public ListInteger prev(TreeNode root) {TreeNode node root;LinkedListTreeNode stack new LinkedList();ListInteger list new ArrayList();while (node ! null || !stack.isEmpty()) {if (node ! null) {stack.push(node);list.add(node.val);node node.left;}else {TreeNode tp stack.pop();node tp.right;}}return list;}//非递归实现中序遍历public void mid(TreeNode root) {TreeNode node root;LinkedListTreeNode stack new LinkedList();while (node ! null || !stack.isEmpty()) {if (node ! null) {stack.push(node);node node.left;}else {TreeNode tp stack.pop();System.out.print(tp.val );node tp.right;}}System.out.println();}//非递归实现后序遍历public ListInteger post(TreeNode root) {TreeNode node root;TreeNode pop null;ListInteger list new ArrayList();LinkedListTreeNode stack new LinkedList();while ( node ! null || !stack.isEmpty()) {if (node ! null) {stack.push(node);node node.left;}else {TreeNode tp stack.peek();if (tp.right null || tp.right pop) {pop stack.pop();list.add(pop.val);}else {node tp.right;}}}return list;}//判断对称二叉树public boolean isSymmetry(TreeNode root) {return isSymmetryRecursion(root.left,root.right);}private boolean isSymmetryRecursion(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 isSymmetryRecursion(left.left,right.right) isSymmetryRecursion(left.right,right.left);}//用递归方式求树的最大深度public int maximumDepthRecursion(TreeNode node) {if (node null) {return 0;}int l maximumDepth(node.left);int r maximumDepth(node.right);return Math.max(l,r) 1;}//用非递归方式求树的最大深度public int maximumDepth(TreeNode root) {TreeNode curr root;LinkedListTreeNode stack new LinkedList();int max 0;TreeNode pop null;while (curr ! null || !stack.isEmpty()) {if (curr ! null) {stack.push(curr);curr curr.left;if (max stack.size()) {max stack.size();}} else {TreeNode peek stack.peek();if ( peek.right null || peek.right pop ) {pop stack.pop();}else {curr peek.right;}}}return max;}//使用层序遍历求树的最大深度public int sequenceMaxDepth(TreeNode root) {if (root null) {return 0;}LinkedListTreeNode queue new LinkedList();queue.offer(root);int depth 0;while ( !queue.isEmpty()) {int size queue.size();for (int j 0; j size; j) {TreeNode tp queue.poll();if (tp.left ! null) {queue.offer(tp.left);}if (tp.right ! null) {queue.offer(tp.right);}//System.out.print(tp.val );}//System.out.println();depth;}return depth;}//使用递归求树的最小深度public int minDepth(TreeNode node) {if (node null) {return 0;}int l minDepth(node.left);int r minDepth(node.right);if (l 0) {return r 1;}if (r 0) {return l 1;}return Math.min(l,r) 1;}//使用层序遍历求得树的最小深度public int sequenceMinDepth(TreeNode root) {LinkedListTreeNode queue new LinkedList();queue.offer(root);int depth 0;while (!queue.isEmpty()) {depth;int size queue.size();for (int i 0; i size ; i) {TreeNode poll queue.poll();if (poll.right null poll.left null) {return depth;}if (poll.left ! null) {queue.offer(poll.left);}if (poll.right ! null) {queue.offer(poll.right);}}}return depth;}//翻转二叉树public void rollbackRecursion(TreeNode node) {if (node null) {return;}TreeNode temp node.left;node.left node.right;node.right temp;rollbackRecursion(node.left);rollbackRecursion(node.right);}}
