做外贸如何访问国外网站,企业网站维护报价,京口区建设局网站,哪里可以学做网站博主简介#xff1a;努力学习的22级计算机科学与技术本科生一枚#x1f338;博主主页#xff1a; 是瑶瑶子啦每日一言#x1f33c;: 所谓自由#xff0c;不是随心所欲#xff0c;而是自我主宰。——康德 目录 一、二叉树刷题纲领二、刷题1、104. 二叉树的最大深度2、 二叉… 博主简介努力学习的22级计算机科学与技术本科生一枚博主主页 是瑶瑶子啦每日一言: 所谓自由不是随心所欲而是自我主宰。——康德 目录 一、二叉树刷题纲领二、刷题1、104. 二叉树的最大深度2、 二叉树的前序遍历非递归3、 二叉树的直径 一、二叉树刷题纲领 二叉树解题的思维模式分两类 1、是否可以通过遍历一遍二叉树得到答案如果可以用一个 traverse 函数配合外部变量来实现这叫「遍历」的思维模式。(对应回溯算法 void traverse(TreeNode root) {if (root null) {return;}// 前序位置traverse(root.left);// 中序位置traverse(root.right);// 后序位置
} 2、是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值这叫「分解问题」的思维模式。对应动态规划算法 前中后序 所谓前序位置就是刚进入一个节点元素的时候后序位置就是即将离开一个节点元素的时候那么进一步你把代码写在不同位置代码执行的时机也不同前序位置的代码只能从函数参数中获取父节点传递来的数据而后序位置的代码不仅可以获取参数数据还可以获取到子树通过函数返回值传递回来的数据。二叉树的所有问题就是让你在前中后序位置注入巧妙的代码逻辑去达到自己的目的你只需要单独思考每一个节点应该做什么其他的不用你管抛给二叉树遍历框架递归会在所有节点上做相同的操作。 一道二叉树的题目时的通用思考过程 是否可以通过遍历一遍二叉树得到答案如果可以用一个 traverse 函数配合外部变量来实现。 是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值。 无论使用哪一种思维模式你都要明白二叉树的每一个节点需要做什么需要在什么时候前中后序做。
二、刷题
1、104. 二叉树的最大深度
104. 二叉树的最大深度 思路分解成子问题maxDepth 1 左子树最大高度右子树最大高度 ♀️代码 public int maxDepth(TreeNode root) {//临界条件if(root null){return 0;}int leftHeight maxDepth(root.left);//求左子树最大高度int rightHeight maxDepth(root.right);//求右子树最大高度return 1 Math.max(leftHeight, rightHeight);}2、 二叉树的前序遍历非递归
144. 二叉树的前序遍历 思路分解成子问题递归序列 add(自身节点 add(左子树的递归序列 add(右子树的递归序列 ♀️代码 public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new LinkedList();if(root null){return ret;}ret.add(root.val);if(root.left!null){ListInteger leftList preorderTraversal(root.left);ret.addAll(leftList);}if(root.right!null){ListInteger rightList preorderTraversal(root.right);ret.addAll(rightList);}return ret;}3、 二叉树的直径
543. 二叉树的直径 思路两种模式的结合首先大的背景是利用maxDepth进行二叉树的后序遍历求当前节点左右子树的最大高度.注意需要一个外部变量maxDiameter来时刻更新最大直径。这种思路是O(n)的时间复杂度可以用遍历每个节点求当前节点的最大直径思路是一样的但是复杂度度是O(n2)因为在本方法中在求maxDepth的时候就已经顺带遍历了整个节点 ♀️代码 public int maxDiameter;public int diameterOfBinaryTree(TreeNode root) {maxDepth(root);return maxDiameter;}public int maxDepth(TreeNode root) {if(root null){return 0;}//计算当前节点的左子树最大高度int leftH maxDepth(root.left);//计算当前节点的右子树的最大高度int rightH maxDepth(root.right);maxDiameter Math.max(maxDiameter,leftH rightH);//更新maxDiameterreturn 1 Math.max(leftH, rightH);}若有不懂的地方欢迎随时在评论区or私信找瑶瑶子交流讨论 Java岛冒险记【从小白到大佬之路】 LeetCode每日一题–进击大厂 Go语言核心编程 算法
