文章目录
- 前言
- 一、四种遍历方式
- 二、二叉树的基本操作
- 2.1 统计二叉树的结点个数
- 2.2 统计二叉树的叶子结点个数
- 2.3 求二叉树第K层节点个数
- 2.4 求二叉树的高度
- 2.5 判断一棵树中是否包含指定的值
- 三、二叉树的基础面试题
- 3.1 相同的树
- 3.2 另一棵树的子树
- 3.3 平衡二叉树
- 总结
前言
上一篇博主归纳了一下二叉树的基本概念以及性质：
二叉树的概念及性质
本文将附上博主自己手动实现的二叉树常见的各种操作以及归纳总结一下常见的基础面试题。
一、四种遍历方式
二叉树额所有问题最终都是四种遍历方式的衍生问题。
前、中、后序遍历为深度优先遍历（DFS），借助“栈”结构
如图：
1.前序遍历：
ABDEGHCF
先访问根节点，然后递归访问左子树，再递归访问右子树，根左右
递归写法：
代码语言：javascript复制public class PreorderTraversal {
List<Integer> ret = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null){
return ret;
}
ret.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return ret;
}
}迭代写法：
代码语言：javascript复制public class Preorder {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>(); //借助辅助栈
public List<Integer> preorder(TreeNode root) {
if (root == null){
return list;
}
TreeNode cur = root;
while (!stack.isEmpty() || cur!=null){ //右边这个条件是防止弹出根节点后，右子树还有结点的情况
while (cur!=null){
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
// 走到这里的时候左子树已经走到了最左下，该弹出最坐下结点，开始访问右子树了
cur=stack.pop();
cur = cur.right;
}
return list;
}
}2.中序遍历：
DBGHEACF
先递归左子树，再根，最后递归右子树，左根右 => 先一路向左走到根儿~’
递归写法：
代码语言：javascript复制public class InorderTraversal {
List<Integer> ret = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root==null) {
return ret;
}
inorderTraversal(root.left);
ret.add(root.val);
inorderTraversal(root.right);
return ret;
}
}迭代写法：
代码语言：javascript复制public class InorderTraversal {
public List<Integer> inorder(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
if (root == null){
return list;
}
TreeNode cur = root;
while (!stack.isEmpty() || cur!=null){
while (cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
}3.后序遍历：
DHGEBFCA
先递归左子树再递归右子树，最后根先一路向左走到根儿~~
递归写法：
代码语言：javascript复制public class PostorderTraversal {
List<Integer> ret=new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root==null){
return ret;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
ret.add(root.val);
return ret;
}
}迭代写法：
代码语言：javascript复制public class Postorder {
public List<Integer> postorder(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
/**
* 前面都一样走到最左边，后面加个if判断：每次弹栈就判断当前结点是否应该处理结束，若右子树为空或者右子树处理过了，那就处理当前
*/
if (root.right == null || root.right == prev) {
res.add(root.val); //当前root结点就是已经处理结束的结点
prev = root; //所以 prev指向了最新的处理结束的结点，以前的不管了反正都结束了
root = null;
} else { //否则，把当前结点压回栈中
stack.push(root);
root = root.right;
}
}
return res;
}
}层序遍历为广度优先遍历（BFS），借助队列结构
4.层序遍历：
从二叉树的第一层开始一层层向下遍历，每一层由左至右开始遍历
ABCDEFGH
代码语言：javascript复制 public void levelOrder(TreeNode<E> root) {
Deque<TreeNode<E>> queue = new LinkedList<>();
queue.offer(root);
// 循环的终止条件就是队列为空
while (!queue.isEmpty()) {
// 取出当前层的节点个数，每当进行下一次遍历的时候，队列中就存储了该层的所有元素
int n = queue.size();
for (int i = 0; i < n; i ) {
TreeNode<E> node = queue.poll();
System.out.print(node.val " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}递归把握语义，巧妙使用递归函数的作用帮助我们辅助解决问题。
注意事项：
1.先序遍历的第一个结果一定是当前二叉树的根节点 2.中序遍历左子树的结果一定再根节点左侧，右子树的遍历结果在根节点右侧 3.后序遍历的最后一个结果是当前二叉树的根节点，将后序遍历的结果集reverse得到一个先序遍历的镜像结果集 “根右左”
二、二叉树的基本操作
2.1 统计二叉树的结点个数
递归：
代码语言：javascript复制public int getNodes(TreeNode<?> root) {
return root == null ? 0 : 1 getNodes(root.left) getNodes(root.right);
}非递归：
代码语言：javascript复制public int getNodesNonRecursion(TreeNode<?> root) {
if (root == null) {
return 0;
}
Deque<TreeNode<?>> queue = new LinkedList<>();
queue.offer(root);
int num = 0;
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
num ;
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
return num;
}2.2 统计二叉树的叶子结点个数
总叶子结点个数 = 左树中的叶子结点个数 右树中的叶子结点个数
代码如下：
代码语言：javascript复制public int getLeafNodes(TreeNode<?> root) {
// 1.边界
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
// 只有root,root就是一个叶子结点
return 1;
}
// 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 右树中的叶子结点个数
return getLeafNodes(root.left) getLeafNodes(root.right);
}2.3 求二叉树第K层节点个数
求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 以root.right为根的第k - 1层结点个数
代码如下：
代码语言：javascript复制 /**
* 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
*
* @return
*/
public int getKLevelNodes(TreeNode root, int k) {
// 1.边界条件
if (root == null || k <= 0) {
return 0;
}
if (k == 1) {
return 1;
}
// 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 以root.right为根的第k - 1层结点个数
return getKLevelNodes(root.left, k - 1) getKLevelNodes(root.right, k - 1);
}2.4 求二叉树的高度
当前树高等于1 左右子树中的最大树高
代码如下：
代码语言：javascript复制/**
* 传入一颗以root为根的二叉树，就能求出该树的高度是多少
*
* @param root
* @return
*/
public int height(TreeNode root) {
if (root == null) {
return 0;
}
return 1 Math.max(height(root.left), height(root.right));
}2.5 判断一棵树中是否包含指定的值
代码如下：
代码语言：javascript复制/**
* 判断以root为根的二叉树中是否包含指定值val
*
* @param root
* @param val
* @return
*/
public boolean contains(TreeNode<E> root, E val) {
if (root == null) {
return false;
}
if (root.val.equals(val)) {
return true;
}
// 继续在左子树和右子树中寻找是否包含指定值
return contains(root.left, val) || contains(root.right, val);
}三、二叉树的基础面试题
3.1 相同的树
思路：
相同的树就是当前结点相同并且其左右子树的结点也相同，递归实现十分容易。
代码如下：
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p==null){
if (q==null){return true;}
return false;
}
if (q==null){
if (p==null){return true;}
return false;
}
if (p.val== q.val){
return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
}
return false;
}
}3.2 另一棵树的子树
思路：
本题基于上一题，然后从根节点先序遍历来逐一判断当前结点是否为相同的树。
- 判断root和subRoot是不是就是相同的树 true
- root.left或者root.right 中判断是否包含subRoot
判断root中是否包含subRoot => root和subRoot就是相同的树 || root.left中是否包含subRoot || root.right中是否包含subRoot
这三个条件有一个满足，就认为root包含subRoot
代码如下：
代码语言：javascript复制public boolean isSameTree(TreeNode p, TreeNode q) {
if (p==null){
if (q==null){return true;}
return false;
}
if (q==null){
if (p==null){return true;}
return false;
}
if (p.val== q.val){
return (isSameTree(p.left,q.left)) && (isSameTree(p.right,q.right));
}
return false;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// 边界
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
// 恰好root和subRoot就是相同的树 => true
if (isSameTree(root,subRoot)){
return true;
}
if (isSubtree(root.left,subRoot)){
return true;
}
if (isSubtree(root.right,subRoot)){
return true;
}
return false;
// return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}3.3 平衡二叉树
public int treeTall(TreeNode root){
if (root==null){
return 0;
}
return 1 Math.max(treeTall(root.left),treeTall(root.right));
}
public boolean isBalanced(TreeNode root) {
if (root==null){
return true;
}
if(Math.abs(treeTall(root.left)-treeTall(root.right))<=1){
return isBalanced(root.left) && isBalanced(root.right);
}
return false;
}总结
以上是二叉树的常见操作以及基础面试题，博主之后会更新二叉树的进阶面试题，于
