数据结构之二叉树及面试题讲解（一）+https://developer.aliyun.com/article/1413553
3，后序遍历
public void postOrder(TreeNode root) { // 空树 直接返回 if(root == null) return; postOrder(root.lChild); postOrder(root.rChild); System.out.print(root.val+" "); }
https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/
代码实现
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root == null) return list; // 遍历左子树 List<Integer> leftTree = postorderTraversal(root.left); list.addAll(leftTree); // 遍历右子树 List<Integer> rightTree = postorderTraversal(root.right); list.addAll(rightTree); list.add(root.val); return list; }
4.层序遍历
使用队列来模拟实现（自己画图想一下，很简单）
/** * 层序遍历 一层一层的遍历 打印 * 先遇到 先打印 fifo 先进先出 使用队列存储遍历的结点 * @param root */ // 层序遍历 public void levelOrder(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.lChild != null) { queue.offer(cur.lChild); } if (cur.rChild != null) { queue.offer(cur.rChild); } } }
https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/
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()) { List<Integer> tmpList = new ArrayList<>(); // 记录当前队列中的结点个数 决定了当前层的tmpList存储的结点个数 也方便添加后序的孩子节点 int size = queue.size(); while(size > 0) { TreeNode cur = queue.poll(); if(cur.left != null) queue.offer(cur.left); if(cur.right != null) queue.offer(cur.right); tmpList.add(cur.val); size--; } ret.add(tmpList); } return ret; }
3.二叉树的基本操作
5.求结点个数
最基本的思路就是定义一个计数器，遍历每一个结点，遍历的方法可以是前序，中序，后序，层序，下面实现两种：递归实现和子问题思路
注：这里的递归实现采用了前序遍历的方式
/** * 求size 遍历每一个结点 设置一个计数器 */ public int size = 0; public int getSize(TreeNode root) { // 空树 直接返回 结点数为1 if(root == null) return 0; size++; getSize(root.lChild); getSize(root.rChild); return size; } // 子问题思路：结点的个数 == 左子树的节点个数+右子树的结点个数+根节点 public int getSize2(TreeNode root) { if(root == null) return 0; return getSize2(root.lChild) + getSize2(root.rChild) + 1; }
6.求叶子节点的个数
叶子节点即左右孩子都为空的结点，要求叶子节点的个数，需要遍历寻找；
/** * 求叶子节点的个数 * 1.遍历实现 满足左右节点都为空 ++ * 2.子问题思路：root叶子节点的个数 == 左子树叶子节点的个数+右子树叶子节点的个数 */ public int leafSize = 0; public int getLeafSize(TreeNode root) { // 递归结束条件 这其实是二叉树的一种情况 // 二叉树有两类 空树 和非空树 // 空树 没有叶子结点 返回0 if(root == null) return 0; if (root.lChild == null && root.rChild == null) { leafSize++; } getLeafSize(root.lChild); getLeafSize(root.rChild); return leafSize; } public int getLeafSize2(TreeNode root) { // 子问题思路 // root叶子节点的个数 == 左子树叶子节点的个数+右子树叶子节点的个数 if(root == null) return 0; if(root.lChild == null && root.rChild == null) return 1; return getLeafSize2(root.lChild) + getLeafSize2(root.rChild); }
7.求第k层的结点个数
转化为子问题思路
/** * 获取第k层结点的个数 * 子问题思路：等价于左树第k-1层和右树第k-1层结点的个数 * 一直走到第k层 * @param root * @param k * @return */ public int getKLevelNodeConut(TreeNode root,int k) { if(root == null) return 0; // 等于1 证明走到了第k层 现在就是第k层的某一个节点 if(k == 1) return 1; return getKLevelNodeConut(root.lChild,k-1) + getKLevelNodeConut(root.rChild,k-1); }
8.求树的高度
子问题思路：树的高度 = 左树和右树高度的最大值+1
// 这种方法可以通过 递归只计算了一次 public int getHeight(TreeNode root) { // 想好递归条件 最后一定是走到null结点 其高度为0 往回归 if(root == null) return 0; int leftHeight = getHeight(root.lChild); int rightHeight = getHeight(root.rChild); return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1; }
9.判断是否包含某节点
先判断根节点 再去遍历左子树 左子树包含 直接返回 不包含 遍历右子树
/** * 判断是否含有某个值的结点 */ public boolean find(TreeNode root,char val) { // 为空 直接返回 if(root == null) return false; if(root.val == val) return true; // 遍历左子树 如果找到，则flg1为true 直接返回即可 不需要再去遍历右子树 boolean flg1 = find(root.lChild,val); if(flg1) return true; // 遍历右子树 boolean flg2 = find(root.rChild,val); if(flg2) return true; return false; }
10.判断是否是完全二叉树
利用层序遍历的思路，把当前结点的所有孩子结点都加入(如果孩子节点是null也会被插入)，当遇到null时，如果是完全二叉树，则此结点一定是最后一个节点，即queue.size == 0,如果不是完全二叉树，则queue.size != 0
/** * 判断是否是完全二叉树 * 层序遍历的思路 把所有结点的左右孩子节点都存入到queue中 如果遇到null 去判断是否还存在元素 * 存在 -- 不是完全二叉树 * @param root * @return */ public boolean iscompleteTree(TreeNode root) { if(root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); // 如果queue中存储的是null 它会被存储到queue中 但却不算有效数据个数 if (cur == null) { if(queue.size() != 0) { return false; } } queue.offer(cur.lChild); queue.offer(cur.rChild); } return true; }
三.二叉树的相关OJ题目
二叉树作为面试中常考的题目有一定的难度(且难度不小)，需要认真去练习，总结
1.判断两棵树是否相同
https://leetcode.cn/problems/same-tree/submissions/
思路分析：
这题可以采用子问题思路 先分析判断的思路，先判断结构上是否一致，如果一致，再去判断值是否相同
- 如果一个为空，一个不为空，结构上不同 返回false
- 如果两个都为空 返回true
- 如果结构上完全相同，去判断值是否相同
代码实现
// 先判断当前所在根是否相同 不同 判断左结点 再判断右节点 // 不同 值不同 一个为空，一个不为空 // 相同 值相同 或者两个都为空 // 一个为空，一个不为空 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.left,q.left) && isSameTree(p.right,q.right);
2.另一棵树的子树
https://leetcode.cn/problems/subtree-of-another-tree/description/
思路分析
- 先判断root是否是null，为空直接返回false
- 判断当前根节点是否和subRoot是否是相同的树
- 再去递归遍历root的左树和右数是否和subRoot是相同的树
代码实现
class Solution { private 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.left,q.left) && isSameTree(p.right,q.right); } public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root == null ) return false; // 判断当前节点是否满足条件 if(isSameTree(root,subRoot)) return true; // 递归遍历左树和右树 if(isSubtree(root.left,subRoot)) return true; if(isSubtree(root.right,subRoot)) return true; // 走到这里 说明以上情况都不满足 直接返回false; return false; } }
数据结构之二叉树及面试题讲解（三）+https://developer.aliyun.com/article/1413556
