基础二叉树算法题（带讲解）

目录

1.检查两颗树是否相同

2.判断这课树是否为另一颗树的子树

3.翻转二叉树

4.对称二叉树

1.检查两颗树是否相同

有树A和树B检查两颗树是否相同呢？

分析：两颗树是否相同需要先判断两棵树结构是否相同，在确认包含的值是否相同。

如：从根结点开始，A的根和B的根都不为空或者都为空则结构相同，若A和B一个为空一个不为空则结构不同为false，基于这种逻辑使用前序遍历进行遍历，

//判断两个树是否相同 public boolean isSameTree(TreeNode p,TreeNode q){ if ((p != null && q == null)|| (p == null && q != null)){ return false; } if (p==null && q==null){ return true; } if (p.val != q.val){ return false; } return isSameTree(p.leftTree,q.leftTree) && isSameTree(p.rightTree,q.rightTree); }

2.判断这课树是否为另一颗树的子树

有树A和树B，B树是否为A的子树呢？

分析：首先判断A树和B树是否相同，相同则B树是A树的子树，不同则对A使用前序遍历到下一个节点来和B树进行判断，代码上还是和上一题还是很像的

//判断一颗树是否为另一颗的子树 public boolean isSubTree(TreeNode root,TreeNode subroot){ if (root == null){ return false; } if (isSameTree(root,subroot)){ return true; } if (isSubTree(root.leftTree,subroot)){ return true; } if (isSubTree(root.rightTree,subroot)){ return true; } return false; }

3.翻转二叉树

如何将二叉树的左子树和右子树互换呢？

分析：定义一个变量tmp用来交换左右子树的地址，然后使用递归前序遍历，

public TreeNode invertTree(TreeNode root){ if (root == null ){ return null; } TreeNode tmd = root.leftTree; root.leftTree = root.rightTree; root.rightTree = tmd; invertTree(root.leftTree); invertTree(root.rightTree); return root; }

4.对称二叉树

判断一颗二叉树为对称的。

分析：使用第一题两颗树是否相同的思路做，但有一些小改动，如我是需要左子树的左结点和右子树的右结点相等，其中我们还需要提取出左右子树的地址用另一个函数来实现，

//对称二叉树 public boolean isSymmetric(TreeNode root){ if (root == null){ return true; } return isSymmetricChild(root.leftTree,root.rightTree); } public boolean isSymmetricChild(TreeNode left,TreeNode right){ if ((left != null && right == null) || (left == null && right != null)){ return false; } if (left == null && right == null){ return true; } if (left.val != right.val){ return false; } return isSymmetricChild(left.leftTree,right.rightTree) && isSymmetricChild(left.rightTree,right.leftTree); }