今天题目不算难我们来个二叉树大集合T94二叉树的中序遍历题目理解给定一个二叉树根节点root返回它的中序遍历结果。核心思路递归递归的本质当前节点的结果 左子树结果 当前节点 右子树结果每次调用dfs(node)其实是在做遍历“以 node 为根的整棵子树”代码实现//创建结果集合ListIntegerresnewArrayList();//调用递归函数dfs(root,res);//返回结果returnres;//中序遍历privatevoiddfs(TreeNodenode,ListIntegerres){//中止条件节点为空if(nodenull){return;}//遍历左子树dfs(node.left,res);//中间res.add(node.val);//右dfs(node.right,res);}题目感悟第一次接触树结构有一些语法需要熟悉比如TreeNode感觉着这就像基础数据需要记牢并没有考察太大的思维点。流程创建List集合存放数据定义中序遍历函数dfs——终止条件左遍历访问中间节点右遍历。T104:二叉树的最大深度题目要求求二叉树的最大深度核心思想本题挺简单的就只有一个小易错点不要将返回的长度忘记1也就是忘了把根节点加上去。代码实现classSolution{publicintmaxDepth(TreeNoderoot){// 终止条件空节点深度为0if(rootnull){return0;}// 递归计算左子树深度intleftDepthmaxDepth(root.left);// 递归计算右子树深度intrightDepthmaxDepth(root.right);// 返回最大深度 当前节点returnMath.max(leftDepth,rightDepth)1;}}本题感悟别忘了1查找树深度的语法为maxDepthT226翻转二叉树题目要求给你一棵二叉树的根节点 root翻转这棵二叉树并返回其根节点。简单来说就是将左子树与右子树进行位置互换纠正一个概念我第一下看到返回值是一串数字下意识认为需要创建一个结果集合来存放结果。但其实只需要return root就行了。rootroot 一个数字比如 4❌ 这个理解是不对的root是节点对象里面包含三种元素root{val:4,left:(节点2),right:(节点7)}代码实现classSolution{publicTreeNodeinvertTree(TreeNoderoot){// 终止条件if(rootnull){returnnull;}// 交换左右子树TreeNodetemproot.left;root.leftroot.right;root.righttemp;// 递归翻转左右子树invertTree(root.left);invertTree(root.right);returnroot;}}本题感悟递归思想自己调用自己T101对称二叉树题目要求给你一个二叉树的根节点 root 检查它是否轴对称。核心思路本题不是遍历一颗树而是同时比较两颗镜像树一句话核心左子树的左 右子树的右左子树的右 右子树的左代码实现classSolution{publicbooleanisSymmetric(TreeNoderoot){// 空树一定对称if(rootnull)returntrue;// 比较左右子树returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleft,TreeNoderight){// 情况1都为空 → 对称if(leftnullrightnull){returntrue;}// 情况2一个为空一个不为空 → 不对称if(leftnull||rightnull){returnfalse;}// 情况3值不相等 → 不对称if(left.val!right.val){returnfalse;}// 情况4递归比较“镜像位置”returnisMirror(left.left,right.right)isMirror(left.right,right.left);}}本题感悟比较的概念是左子树的左 右子树的右 左子树的右 右子树的左关于是否镜像对称的判断,分为5步:1.root是否为空 2.是否都为空3.是否一个是空一个不是空 4.左右值是否相等 5.继续递归比较
【LeetCodehot100】二叉树大合集 T94：二叉树的中序遍历 T104:二叉树的最大深度 T226：翻转二叉树 T101：对称二叉树
今天题目不算难我们来个二叉树大集合T94二叉树的中序遍历题目理解给定一个二叉树根节点root返回它的中序遍历结果。核心思路递归递归的本质当前节点的结果 左子树结果 当前节点 右子树结果每次调用dfs(node)其实是在做遍历“以 node 为根的整棵子树”代码实现//创建结果集合ListIntegerresnewArrayList();//调用递归函数dfs(root,res);//返回结果returnres;//中序遍历privatevoiddfs(TreeNodenode,ListIntegerres){//中止条件节点为空if(nodenull){return;}//遍历左子树dfs(node.left,res);//中间res.add(node.val);//右dfs(node.right,res);}题目感悟第一次接触树结构有一些语法需要熟悉比如TreeNode感觉着这就像基础数据需要记牢并没有考察太大的思维点。流程创建List集合存放数据定义中序遍历函数dfs——终止条件左遍历访问中间节点右遍历。T104:二叉树的最大深度题目要求求二叉树的最大深度核心思想本题挺简单的就只有一个小易错点不要将返回的长度忘记1也就是忘了把根节点加上去。代码实现classSolution{publicintmaxDepth(TreeNoderoot){// 终止条件空节点深度为0if(rootnull){return0;}// 递归计算左子树深度intleftDepthmaxDepth(root.left);// 递归计算右子树深度intrightDepthmaxDepth(root.right);// 返回最大深度 当前节点returnMath.max(leftDepth,rightDepth)1;}}本题感悟别忘了1查找树深度的语法为maxDepthT226翻转二叉树题目要求给你一棵二叉树的根节点 root翻转这棵二叉树并返回其根节点。简单来说就是将左子树与右子树进行位置互换纠正一个概念我第一下看到返回值是一串数字下意识认为需要创建一个结果集合来存放结果。但其实只需要return root就行了。rootroot 一个数字比如 4❌ 这个理解是不对的root是节点对象里面包含三种元素root{val:4,left:(节点2),right:(节点7)}代码实现classSolution{publicTreeNodeinvertTree(TreeNoderoot){// 终止条件if(rootnull){returnnull;}// 交换左右子树TreeNodetemproot.left;root.leftroot.right;root.righttemp;// 递归翻转左右子树invertTree(root.left);invertTree(root.right);returnroot;}}本题感悟递归思想自己调用自己T101对称二叉树题目要求给你一个二叉树的根节点 root 检查它是否轴对称。核心思路本题不是遍历一颗树而是同时比较两颗镜像树一句话核心左子树的左 右子树的右左子树的右 右子树的左代码实现classSolution{publicbooleanisSymmetric(TreeNoderoot){// 空树一定对称if(rootnull)returntrue;// 比较左右子树returnisMirror(root.left,root.right);}privatebooleanisMirror(TreeNodeleft,TreeNoderight){// 情况1都为空 → 对称if(leftnullrightnull){returntrue;}// 情况2一个为空一个不为空 → 不对称if(leftnull||rightnull){returnfalse;}// 情况3值不相等 → 不对称if(left.val!right.val){returnfalse;}// 情况4递归比较“镜像位置”returnisMirror(left.left,right.right)isMirror(left.right,right.left);}}本题感悟比较的概念是左子树的左 右子树的右 左子树的右 右子树的左关于是否镜像对称的判断,分为5步:1.root是否为空 2.是否都为空3.是否一个是空一个不是空 4.左右值是否相等 5.继续递归比较
