文章目录1. 判断相同的树LC100题目描述解题思路代码示例2. 另一棵树的子树LC572题目描述解题思路代码示例3. 翻转二叉树LC226题目描述解题思路代码示例4. 平衡二叉树(LC110)题目描述解题思路代码示例优化时间复杂度O(n)5. 对称二叉树LC101题目描述解题思路代码示例1. 判断相同的树LC100判断相同的树题目描述解题思路先判断结构如果不是都为空或者都为非空返回false如果结构相同且不为空则判断数值是否相等不等则返回false如果结构相等且为空返回true当前节点判断完后判断左子树和右子树是否相等代码示例classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//判断结构if(!(pnullqnull||p!nullq!null))returnfalse;//判断数值if(p!null(p.val!q.val))returnfalse;elseif(pnull)returntrue;returnisSameTree(p.left,q.left)isSameTree(p.right,q.right);}}2. 另一棵树的子树LC572另一棵树的子树题目描述解题思路检查是否为子树就是检查root中是否有子树与subtree相同可以借用前一个题的方法。如果根节点为空返回false如果当前根节点以下的树与subtree相等则返回true接着检查根节点的左子树或右子树是否与subtree相等代码示例publicbooleanisSubtree(TreeNoderoot,TreeNodesubRoot){if(rootnull)returnfalse;if(isSameTree(root,subRoot))returntrue;returnisSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);}3. 翻转二叉树LC226翻转二叉树题目描述解题思路如果root为空返回空利用前序遍历先交换根节点的左右节点再调用本身分别交换左右两个子树的节点返回root代码示例publicTreeNodeinvertTree(TreeNoderoot){if(rootnull)returnnull;TreeNodetmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);returnroot;}4. 平衡二叉树(LC110)平衡二叉树题目描述解题思路先求长度再判断两子树高度差是否小于2。时间复杂度O n 2 n^2n2时间复杂度高是因为每一个节点作为根节点其子树的高度都会被计算一次代码示例intgetHeight(TreeNoderoot){if(rootnull)return0;if(root.leftnullroot.rightnull)return1;intleftNgetHeight(root.left);intrightNgetHeight(root.right);returnMath.max(leftN,rightN)1;}publicbooleanisBalanced(TreeNoderoot){if(rootnull)returntrue;intleftNgetHeight(root.left);intrightNgetHeight(root.right);if(Math.abs(leftN-rightN)1)returnfalse;returnisBalanced(root.left)isBalanced(root.right);优化时间复杂度O(n)getHeight():每求一次的高度都检查左右子树高度差是否小于2不是则返回-1如果接受值为-1则继续返回-1排除以上情况则返回计算的结果isBalanced():判断getHeight()返回值是否为负数intgetHeight(TreeNoderoot){if(rootnull)return0;if(root.leftnullroot.rightnull)return1;intleftNgetHeight(root.left);if(leftN0)return-1;intrightNgetHeight(root.right);if(rightN0)return-1;if(Math.abs(leftN-rightN)2)returnMath.max(leftN,rightN)1;elsereturn-1;}publicbooleanisBalanced(TreeNoderoot){if(rootnull)returntrue;returngetHeight(root)0;}5. 对称二叉树LC101对称二叉树题目描述解题思路把右子树翻转后判断左右子树是否相等代码示例publicbooleanisSymmetric(TreeNoderoot){returnisSameTree(root.left,invertTree(root.right));}