数据结构------二叉树经典习题1

博主主页: 码农派大星.

关注博主带你了解更多数据结构知识

1判断相同的树 OJ链接

---

 这道题相对简单,运用我们常规的递归写法就能轻松写出

所以我们解题思路应该这样想:

1.如果p为空，q为空，那么就是两颗空树肯定相等
2.如果一个树为空另一棵树不为空那么一定不相等
3.如果都不为空，值相同才相等。
4.再递归判断左子树是否相等，右子树是否相等，只有左右子树都相等才是相同的树

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p != null && q == null || p == null  && q != null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p == null && q== null){return true;}//3,都不为空if(p.val != q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

2判断另一课树的子树OJ链接

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

这道题也要用到我们的递归思想

1如果都为空树,则false

2如果俩个树为相同的树,则true

3 再递归看sub是否为左子树的子树，右子树的子树，如果都不是，则返回false

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}//1,判断两个树是不是相同的树if(isSameTree(root,subRoot)){return true;}//2,if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;   }public boolean isSameTree(TreeNode p, TreeNode q) {//1,一个为空一个不为空if(p != null && q == null || p == null  && q != null){return false;}//2,第一步走完要么都为空 要么都不为空 两个都是空if(p == null && q== null){return true;}//3,都不为空if(p.val != q.val){return false;}//4,此时代表两个都不为空,同时val也是一样//5,说明根节点相同,接下来判断两棵树的左 右是不是同时相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}}

 

3翻转二叉树OJ链接 

同样的递归思想,不变的套路

1判断是否为空树

2再用递归交换左右树 

class Solution {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;}
}

4平衡二叉树OJ链接

 

1判断是否空树

2求左树的深度和右树的深度

3判断左树的深度减右树的深度不能大于1

左树和右数的子树也一样

math.abs() 是一个数学函数，它用于返回一个数的绝对值 

class Solution {public boolean isBalanced(TreeNode root) {if(root == null){return true;}return getHeight(root) >= 1;}//获取二叉树高度public int getHeight(TreeNode root){if(root == null){return 0;}int leftHeight = getHeight(root.left);if(leftHeight < 0){return -1;}int rightHeight = getHeight(root.right);if(rightHeight < 0){return -1;}if(Math.abs(leftHeight - rightHeight) <= 1){return Math.max(leftHeight,rightHeight) + 1;}else{return -1;}}
}

5对称二叉树 OJ链接

 

1判断是否根节点为空

2 检查结构是否相同:一个为空一个不为空

3检查结构:两个都为空或两个都不为空

4判断左右根节点是否相同

5开始判断是否对称 递归开始:

满足左子树的左  和 右子树的右  对称 同时 左子树的右  和 右子树的左 对称

class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){//1检查结构是否相同---一个为空一个不为空if(leftTree != null && rightTree == null || leftTree ==null &&rightTree !=null){return false;}//2检查结构---两个都为空或两个都不为空if(leftTree == null && rightTree == null){return true;}//3检查结狗---- 处理两个都为空或两个都不为空if(leftTree.val != rightTree.val){return false;}//4.此时两个引用都不为空而且节点值一样//5开始判断是否对称//6满足左子树的左  和 右子树的右  对称 同时 左子树的右  和 右子树的左 对称return isSymmetricChild(leftTree.left,rightTree.right)&& isSymmetricChild(leftTree.right,rightTree.left);}
}

 6二叉树的层序遍历OJ链接

我们需要借助队列来实现: 

1判空

2 将root入队列,出队时在让root.left(cur.left)和root.right(cur.right)入队

循环这样的操作,知道队列为空

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if(root == null){return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){int size = queue.size();List<Integer> list = new ArrayList<>();while (size > 0){TreeNode cur = queue.poll();list.add(cur.val);if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

7二叉树的遍历OJ链接 

读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

 

 1遍历字符串 跳过"#",其他的字符串都new为新Node,此时字符串就是先序遍历的状态

2遍历字符串的时候，我们要把i设置为成员变量防止每次递归后i从0开始

3.遍历二叉树中序输出

import java.util.Scanner;
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}
}
public class Main {public static int i = 0;public static TreeNode createTree(String str){TreeNode root = null;if(str.charAt(i) != '#'){root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else{i++;}return root;}public static void inorder(TreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.val + " ");inorder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root =  createTree(str);inorder(root);}}
}