网站建设的基础知识与维护,wordpress.php扩张,软件工程师需要学什么,本人急招一名临时工对称的二叉树 思路#xff1a;用递归#xff0c;首先明白递归中止的条件是什么 搬用别人的看法#xff1a;
做递归思考三步#xff1a;
1.递归的函数要干什么#xff1f; 函数的作用是判断传入的两个树是否镜像。 输入#xff1a;TreeNode left, TreeNode right 输出…对称的二叉树 思路用递归首先明白递归中止的条件是什么 搬用别人的看法
做递归思考三步
1.递归的函数要干什么 函数的作用是判断传入的两个树是否镜像。 输入TreeNode left, TreeNode right 输出是true不是false 2.递归停止的条件是什么 左节点和右节点都为空 - 倒底了都长得一样 -true 左节点为空的时候右节点不为空或反之 - 长得不一样- false 左右节点值不相等 - 长得不一样 - false 3.从某层到下一层的关系是什么 要想两棵树镜像那么一棵树左边的左边要和二棵树右边的右边镜像一棵树左边的右边要和二棵树右边的左边镜像 调用递归函数传入左左和右右 调用递归函数传入左右和右左 只有左左和右右镜像且左右和右左镜像的时候我们才能说这两棵树是镜像的 调用递归函数我们想知道它的左右孩子是否镜像传入的值是root的左孩子和右孩子。这之前记得判个rootnull。 代码如下
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(rootnull) {return true;}return compare(root.left,root.right);}public boolean compare(TreeNode left,TreeNode right) {if(leftnullrightnull) {return true;}if(left!nullrightnull) {return false;}if(leftnullright!null) {return false;}return (left.valright.val)compare(left.right,right.left)compare(left.left,right.right);//左左镜像和右右镜像且左右镜像和右左镜像值也相等的时候才是镜像的}}青蛙跳台阶问题–简单动态规划 思路通过找规律可以发现当n0输出为1n1输出为1n2输出为2n3输出为3n4输出为5类似于斐波那契Fibonacci数列 有一个小知识点
class Solution {public int numWays(int n) {int[] arrnew int[200];arr[0]1;arr[1]1;for(int i2;in;i) {arr[i](arr[i-1]arr[i-2])%1000000007;//找规律}return arr[n]; }
}