【算法日记】二叉树：判断相同树和子树，翻转二叉树，平衡二叉树，对称二叉树

文章目录

• 1. 判断相同的树（LC100）
• • 题目描述
  • 解题思路
  • 代码示例
• 2. 另一棵树的子树（LC572）
• • 题目描述
  • 解题思路
  • 代码示例
• 3. 翻转二叉树（LC226）
• • 题目描述
  • 解题思路
  • 代码示例
• 4. 平衡二叉树(LC110)
• • 题目描述
  • 解题思路
  • 代码示例
  • 优化（时间复杂度O(n)）
• 5. 对称二叉树（LC101）
• • 题目描述
  • 解题思路
  • 代码示例

1. 判断相同的树（LC100）

判断相同的树

题目描述

解题思路

1. 先判断结构，如果不是都为空或者都为非空，返回false
2. 如果结构相同且不为空，则判断数值是否相等，不等则返回false
3. 如果结构相等且为空，返回true
4. 当前节点判断完后，判断左子树和右子树是否相等

代码示例

classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//判断结构if(!(p==null&&q==null||p!=null&&q!=null))returnfalse;//判断数值if(p!=null&&(p.val!=q.val))returnfalse;elseif(p==null)returntrue;returnisSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}

2. 另一棵树的子树（LC572）

另一棵树的子树

题目描述

解题思路

1. 检查是否为子树就是检查root中是否有子树与subtree相同，可以借用前一个题的方法。
2. 如果根节点为空，返回false
3. 如果当前根节点以下的树与subtree相等，则返回true
4. 接着检查根节点的左子树或右子树是否与subtree相等

代码示例

publicbooleanisSubtree(TreeNoderoot,TreeNodesubRoot){if(root==null)returnfalse;if(isSameTree(root,subRoot))returntrue;returnisSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);}

3. 翻转二叉树（LC226）

翻转二叉树

题目描述

解题思路

如果root为空，返回空；利用前序遍历，先交换根节点的左右节点，再调用本身分别交换左右两个子树的节点，返回root

代码示例

publicTreeNodeinvertTree(TreeNoderoot){if(root==null)returnnull;TreeNodetmp=root.left;root.left=root.right;root.right=tmp;invertTree(root.left);invertTree(root.right);returnroot;}

4. 平衡二叉树(LC110)

平衡二叉树

题目描述

解题思路

先求长度，再判断两子树高度差是否小于2。时间复杂度O（ n 2 ） （n^2）（n2）
时间复杂度高是因为每一个节点作为根节点，其子树的高度都会被计算一次

代码示例

intgetHeight(TreeNoderoot){if(root==null)return0;if(root.left==null&&root.right==null)return1;intleftN=getHeight(root.left);intrightN=getHeight(root.right);returnMath.max(leftN,rightN)+1;}publicbooleanisBalanced(TreeNoderoot){if(root==null)returntrue;intleftN=getHeight(root.left);intrightN=getHeight(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(root==null)return0;if(root.left==null&&root.right==null)return1;intleftN=getHeight(root.left);if(leftN<0)return-1;intrightN=getHeight(root.right);if(rightN<0)return-1;if(Math.abs(leftN-rightN)<2)returnMath.max(leftN,rightN)+1;elsereturn-1;}publicbooleanisBalanced(TreeNoderoot){if(root==null)returntrue;returngetHeight(root)>=0;}

5. 对称二叉树（LC101）

对称二叉树

题目描述

解题思路

把右子树翻转后判断左右子树是否相等

代码示例

publicbooleanisSymmetric(TreeNoderoot){returnisSameTree(root.left,invertTree(root.right));}