二叉树OJ题（上）

✅每日一练：100. 相同的树 - 力扣（LeetCode）

---

     题目的意思是俩棵树的结构不仅要相同，而且每个节点的值还要相同，如果满足上面2个条件，则成立！

解题思路：

从三个方面去考虑：

1.如果p,q都为空，那么一定相同；

2.如果p为空，q不为空，或者p不为空，q为空，那么一定不相同；

3.如果二者都不为空，那么需要判断根节点，如果根节点不相同，那么一定不相同，如果相同，我们需要比较左右子树的值和左右子树的结构；

代码：

public boolean isSameTree(TreeNode p, TreeNode q) {//如果p,q都为空，那么这2个树一定相同if (p == null && q == null) {return true;}//如果q为空，p不为空，那么一定不相同,或者p为空，q不为空，那么一定不相同if (p != null && q == null||p == null && q != null) {return false;}//如果p,q都不为空，那么要判断值，如果值不相同，那么一定不相同if (p.val != q.val) {return false;}//如果p,q都不为空，并且p,q的值相同，那么要判断p,q的左右子树的值，如果相同为真，反之；return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}

---

✅每日一练：572. 另一棵树的子树 - 力扣（LeetCode）

---

 解题思路：

1.如果根节点为空，那么返回false;

2.如果根节点相同，那么我们需要判断这2棵树是否相同，我们可以借助上面写的isSameTree方法去判断，如果相同，则subRoot是root的子树；

3.如果根节点不相同，我们需要在左子树或者右子树去找是否有和subRoot相同的树；

代码：

public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null||subRoot == null){return false;}//判断2棵树是否相同if(isSameTree(root,subRoot)){return true;}//判断左子树是否有subRootif(isSubtree(root.left,subRoot)){return true;}//判断右子树是否有subRootif(isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//如果p,q都为空，那么这2个树一定相同if (p == null && q == null) {return true;}//如果q为空，p不为空，那么一定不相同if (p != null && q == null) {return false;}//如果p为空，q不为空，那么一定不相同if (p == null && q != null) {return false;}//如果p,q都不为空，那么要判断值，如果值不相同，那么一定不相同if (p.val != q.val) {return false;}//如果p,q都不为空，并且p,q的值相同，那么要判断p,q的左右子树的值，如果相同为真，反之；return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}

---

✅每日一练：226. 翻转二叉树 - 力扣（LeetCode）

---

 

解题思路：

利用递归思想，如果根节点不为空，递归左右子树的值进行交换；

public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;}

---

✅每日一练：110. 平衡二叉树 - 力扣（LeetCode）

---

 

 解题思路：

题目的意思就是每个节点的左右子树的高度差的绝对值不能超过1，就是平衡二叉树，则满足题目需求；

代码：

public boolean isBalanced(TreeNode root) {if(root == null){return true;}int leftH = getHeight(root.left);int rightH =getHeight(root.right);return Math.abs(leftH-rightH)<=1 && isBalanced(root.left) && isBalanced(root.right);}public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

---

✅每日一练：101. 对称二叉树 - 力扣（LeetCode）

 

解题思路：

1.如果根节点为空，那么对称；

2.如果根节点不为空，根节点的左子树为空，根节点的右子树不为空，或者根节点的左子树不为空，根节点的右子树为空，那么一定不对称；

3.如果根节点的左子树的值和右子树的值不相等，那么一定不对称；

4.如果上面条件都没有满足到，那么我们需要判断左子树的左子树是否和右子树的右子树相等，左子树的右子树是否和右子树的左子树相等，如果相等，则对称；

代码：

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

---

✅每日一练：102. 二叉树的层序遍历 - 力扣（LeetCode）

---

 

解题思路：

层序遍历就是从上到下，从左到右逐个遍历，层序遍历相对于其他遍历简单，但是代码实现起来没有那么简单 ，我们可以利用队列去实现他，利用队列先进先出的特点去实现：

首先判断根节点，如果为空就返回，如果不为空，就把根节点放进队列，用while循环来判断当前队列是否为空，再定义一个变量来存放根节点的值，然后打印，打印完再去判断根节点的左右子树，如果不为空，就入队，依次执行下去我们可以得到层序遍历，代码：

public void levelOrder1(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode cur = queue.poll();System.out.print(cur.val + " ");if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}}

这是没有返回值的方法，但是这道oj题的返回值是List<List<Integer>>，所以这是我们就要换种思路来写这题了，大致的思路就是，我们需要2的循环，用当前队列是否为空作为第一个循环条件，当前队列里面元素的个数的大小作为子循环条件，代码：

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();if (root == null) {return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();//用来判断当前队列的大小//System.out.print(cur.val);List<Integer> tmp = new ArrayList<>();while (size != 0) {TreeNode cur = queue.poll();tmp.add(cur.val);size--;if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}list.add(tmp);//将每层的结果放到list中}return list;}