关键词：
题目目录
基础面试题
二叉树的前序遍历
题目：在线OJ
思考：
首先，我们要了解，前序遍历就是按照顺序：根节点—左子树—右子树的方式遍历树(根左右)
在访问左右子树的时候，按照上述同样的方法遍历，因此我们可以考虑使用递归来解决
- 创建一个 List，将根节点的元素加入到 List 中
- 递归遍历左子树，把左子树的遍历结果加入到 List 中
- 递归遍历右子树，把右子树的遍历结果加入到 List 中
- 最后返回这个 List 即可
画图分析：
代码实现：
public List<Integer> preorderTraversal(TreeNode root)
//创建一个 List
List<Integer> result = new ArrayList<>();
if(root == null)
//空树返回 一个空 List(元素个数为空，但不是null)
return result;
//访问根节点
//把元素 add 到 List中
result.add(root.val);
//递归遍历左子树,把左子树的遍历结果加入到List中
result.addAll(preorderTraversal(root.left));
//递归遍历右子树,把右子树的遍历结果加入到List中
result.addAll(preorderTraversal(root.right));
return result;
二叉树的中序遍历
题目：在线OJ
思考：
中序遍历是按照顺序：左子树遍历—根节点—右子树遍历的方式来遍历树(左根右)
同先序遍历一样，使用递归解决
画图分析：
代码实现：
public List<Integer> inorderTraversal(TreeNode root)
//创建一个List
List<Integer> result = new ArrayList<>();
//空树判断
if(root == null)
return result;
//递归遍历左子树
result.addAll(inorderTraversal(root.left));
//根节点
result.add(root.val);
//递归遍历右子树
result.addAll(inorderTraversal(root.right));
return result;
二叉树的后续遍历结果
题目：在线OJ
思考：
后续遍历按照顺序：左子树遍历—右子树遍历—根节点的遍历方式来遍历树的(左右根)
实现过程参考前序遍历
代码实现：
public List<Integer> postorderTraversal(TreeNode root)
//创建一个List
List<Integer> result = new ArrayList<>();
//空树判断
if(root == null)
return result;
//左子树遍历
result.addAll(postorderTraversal(root.left));
//右子树遍历
result.addAll(postorderTraversal(root.right));
//根节点
result.add(root.val);
return result;
相同的树
题目：在线OJ
思考：
- 先判断根节点是否相同
- 遍历判断左子树是否相同
- 遍历判断右子树是否相同
以上条件均满足时，则说明这两棵树相同
画图分析：
代码实现：
public boolean isSameTree(TreeNode p, TreeNode q)
//两棵树全为空
if(p == null && q == null)
return true;
//一棵树为空
if(p == null || q == null)
return false;
//两棵树均不为空
//先判断根节点是否相同
if(p.val != q.val)
return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
另一棵树的子树
题目：在线OJ
思考：
判断一棵树是不是另外一棵树的子树，本质就是在判断一棵树和另外一颗树的某个子树是否相等
可使用：遍历 + 递归拆分问题
- 先检查 root 和 subRoot 是否相等
- 检查 root.left 是否包含 subRoot
- 在检查 root.right 是否包含 subRoot
上述满足一个即可
画图：
上述画了左子树的情况，若左子树在不相同，接着再递归右子树与子树比较，只要符合一种情况即可
代码实现：
public boolean isSubtree(TreeNode root, TreeNode subRoot)
//两棵树都为空
if(root == null && subRoot == null)
return true;
//一棵树为空
if(root == null || subRoot == null)
return false;
boolean ret = false;
//根节点的值 相同
if(root.val == subRoot.val)
ret = isSameTree(root,subRoot);
return ret || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
二叉树的最大深度
题目：在线OJ
思考：
深度即：根节点到最远叶子节点的层数
此处要注意深度是从 0 开始算，还是从 1 开始算
二叉树的最大深度，即：max(左子树深度，右子树深度) + 1
代码实现：
public int maxDepth(TreeNode root)
//空树
if(root == null)
return 0;
//左右子树为空 只有根节点
if(root.left == null && root.right == null)
return 1;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth) ;
平衡二叉树判断
题目：在线OJ
思考：
- 先判断空树，或没有子树(只有根节点)—平衡
- 针对当前节点，求左右子树高度差，看是否 ＞1
- 若 ＜1，再递归判断该树的左右子树，看高度差是否 ＜1
即：一棵树是否平衡，先判断该树自己的左右子树高度差是否 ≤ 1，还要满足左右子树也平衡才可以判断该树是平衡树
画图分析：
代码实现：
public boolean isBalanced(TreeNode root)
//空树
if(root == null)
return true;
//只有根节点 左右子树为空
if(root.left == null && root.right == null)
return true;
//判断当前节点对应的子树是否平衡
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
if(leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
return false;
return isBalanced(root.left) && isBalanced(root.right);
对称二叉树
题目：在线OJ
思考：
判断一棵树是否对称，本质上就是判断该树的所有子树是否对称
- 先判断左右子树( A B )的根节点是否相同
- 判断 A.left 和 B.right 是否成镜像关系
- 判断 A.right 和 B.left 是否成镜像关系
画图分析：
代码实现：
public boolean isSymmetric(TreeNode root)
//空树
if(root == null)
return true;
return isMirror(root.left,root.right);
public boolean isMirror(TreeNode t1,TreeNode t2)
//左右子树都为空
if(t1 == null && t2 == null)
return true;
//一棵子树为空
if(t1 == null || t2 == null)
return false;
//两棵树的根节点 值不相等
if(t1.val != t2.val)
return false;
return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);
进阶面试题
二叉树的遍历及构建
题目：在线OJ
思考：
画图分析：
代码实现：
public class BuildTreeDemo
//静态内部类
static class TreeNode
public char val;
TreeNode left;
TreeNode right;
public TreeNode(char val)
this.val = val;
public static void main(String[] args)
Scanner scan = new Scanner(System.in);
//循环输入 在线OJ 一般都是多组用例
while(scan.hasNext())
// s这个字符串就对应一对形如“abc##de#g##f###” 的输入数据
String s = scan.next();
TreeNode root = build(s);
//中序遍历
inOrder(root);
System.out.println();
private static void inOrder(TreeNode root)
//若为空树，直接返回
if(root == null)
return;
//递归访问左子树
inOrder(root.left);
//访问根节点
System.out.print(root.val+" ");
//递归访问右子树
inOrder(root.right);
// index用来记录访问到 s 的哪个元素
private static int index = 0;
private static TreeNode build(String s)
index = 0;
//先序遍历
return createTreePrevOrder(s);
private static TreeNode createTreePrevOrder(String s)
//获取到当前处理到哪个节点
char cur = s.charAt(index);
if(cur == '#')
return null;
TreeNode root = new TreeNode(cur);
index++;
//下一个节点开始就是当前root左子树的先序遍历结果
root.left = createTreePrevOrder(s);
index++;
root.right = createTreePrevOrder(s);
return root;
部分递归过程分析：
二叉树的分层遍历
题目：在线OJ
- 递归实现
思考：
创建一个变量 result 来存放我们的结果，最后 return result
(result 相当于一个二维数组，result 0 对应第0层节点，result 1 对应第1层节点…)
代码实现：
static List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root)
//清空result 因为result是全局变量
result.clear();
//空树判定
if(root == null)
return null;
// helper 方法辅助递归，第二个参数表示当前层数 从 0 开始算
helper(root,0);
return result;
private void helper(TreeNode root, int level)
if(level == result.size())
result.add(new ArrayList<>());
//把当前节点添加到 result 中的合适位置
result.get(level).add(root.val);
if(root.left != null)
helper(root.left,level + 1);
if(root.right != null)
helper(root.right,level + 1);
代码分析：
- 非递归实现 (循环)
思考：
- 使用一个队列queue，先用来存放每一层的节点，并使用变量 level 来记录该层有几个元素
- 创建一个 list 来存放每一层节点，每遍历完一层，将每一层都入队列然后再出队列并将其移除，即：把队列里这一层的元素出队列，并将其加入到 list 中
- 判断左 / 右节点是否为空，来将下一层的元素加入到queue，队列为空，停止循环
代码实现：
public List<List<Integer>> levelOrder(TreeNode root)
//创建一个 result 来存放结果
List<List<Integer>> result = new ArrayList<>();
//空树判断
if(root == null)
return result;
//创建一个队列，把根节点加入队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//队列不为空，就一直循环
while ( !queue.isEmpty())
//定义为一个 list 来存放每一层节点
List<Integer> list = new ArrayList<>();
//队列中当前所存在的数 即为当前层所有的数
int level = queue.size();
for (int i = 0; i < level; i++)
// 获得并将第一个节点出队列
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null)
queue.add(cur.left);
if(cur.right != null)
queue.add(cur.right);
result.add(list);
return result;
二叉树的最近公共祖先
题目：在线OJ
- 方法1
思考：
若从某个节点开始，后续遍历能把 p 和 q 都找到，说明该节点就是 p 和 q 的公共祖先
若从某个节点开始，后续遍历能把 p 和 q 都找到，并且 p 和 q 不在同一子树中，则当前节点就是 p 和 q 的最近公共祖先
代码实现：
private TreeNode lca = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
//空树判断
if(root == null)
return null;
// findNode方法，在递归寻找的过程中，找到结果，就将结果放到 lca 中
findNode(root,p,q);
//返回 lca
return lca;
//从 root 出发找 p q,只要找到 1 个，就返回true，都找不到返回false
private boolean findNode(TreeNode root, TreeNode p, TreeNode q)
//空树判断
if(root == null)
return false;
// 递归 后序遍历查找
int left = findNode(root.left,p,q) ? 1 : 0;
int right = findNode(root.right,p,q) ? 1 : 0;
int mid = (root == p || root == q) ? 1 : 0;
if(left + right + mid == 2)
lca = root;
return (left + right +数据结构面试题及答案讲解：二叉树专题（上）(代码片段)
数据结构面试题及答案讲解：二叉树专题（上）本节目标1、求二叉树的最大深度。（2018年腾讯面试题）2、判断一个二叉树是否是高度平衡的二叉树。（2020年字节跳动面试真题）3、根据一棵树的前序遍历与中序遍历构造二叉树... 查看详情
面试题：二叉树的镜像(代码片段)
题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / 610 // 57911 镜像二叉树 8 / 106 // 11975代码//二叉树一般用到递归publicclassSolutionpublicvoidMirror(TreeNoderoot)TreeNodetemp;if(root==null)return;if(root!=nul... 查看详情
面试题：平衡二叉树(代码片段)
题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。思路：利用上一题求二叉树的深度publicclassSolutionpublicbooleanIsBalanced_Solution(TreeNoderoot)if(root==null)returntrue;intleft=depth(root.left);intright=depth(root.right);intbalance=le 查看详情
剑指offer:面试题19二叉树的镜像(代码片段)
题目描述操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树8/610//57911镜像二叉树8/106//11975代码示例publicclassOffer19publicstaticvoidmain(String[]args)//构建树TreeNoderoot=newTreeNode(1);root.left=newTreeNode(2);root.right 查看详情
面试题：对称二叉树(代码片段)
题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 0 ... 查看详情
面试题：重建二叉树(代码片段)
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列1,2,4,7,3,5,6,8和中序遍历序列4,7,2,1,5,3,8,6，则重建二叉树并返回。使... 查看详情
面试题28：对称的二叉树(代码片段)
考察二叉树的遍历。判断前序遍历，与新增的前->右->左遍历结果是否一致。C++版#include<iostream>#include<algorithm>usingnamespacestd;//定义二叉树structTreeNodeintval;structTreeNode*left;structTreeNode*right;TreeNode(intval): 查看详情
面试题7：重建二叉树(代码片段)
<?phpheader("content-type:text/html;charset=utf-8");/**重建二叉树P62*/classTreeNodevar$val;var$left=NULL;var$right=NULL;function__construct($val)$this->val=$val;functionreConstructBinaryTree($pre 查看详情
面试题：序列化二叉树(代码片段)
题目描述：请实现两个函数，分别用来序列化和反序列化二叉树思路：遍历publicclassSolutionintindex=-1;StringSerialize(TreeNoderoot)StringBuffersb=newStringBuffer();if(root==null)sb.append("#,");returnsb.toString();sb.append(root.val+" 查看详情
面试题：二叉树的深度(代码片段)
题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。思路：递归//递归publicclassSolutionpublicintTreeDepth(TreeNoderoot)if(root==null)return0;intleft=T... 查看详情
剑指offer面试题27.二叉树的镜像(代码片段)
面试题27.二叉树的镜像 请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如输入： 4 / 2 7 / /1 36 9镜像输出： 4 / 7 &nb 查看详情
面试题：把二叉树打印成多行(代码片段)
题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。思路：借助队列实现importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.Queue;publicclassSolutionArrayList<ArrayList<Integer>>Print(TreeNodepRoo 查看详情
面试题：二叉树的下一个节点(代码片段)
题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路：//包含指向父节点的指针//node.nextnode.leftnode.rightpublicclassSo... 查看详情
剑指offer:面试题07.重建二叉树(代码片段)
1.要点二叉树遍历重复在查找中查找某个数时（重复+查找=二重循环），应考虑是否可以用map2.题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。3.示... 查看详情
面试题37.序列化二叉树(代码片段)
题目： 解答：1/**2*Definitionforabinarytreenode.3*structTreeNode4*intval;5*TreeNode*left;6*TreeNode*right;7*TreeNode(intx):val(x),left(NULL),right(NULL)8*;9*/10classCodec11public:1213//Encod 查看详情
面试题：从上往下打印二叉树(代码片段)
题目描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。树的按层遍历思路：辅助队列保存每个节点的子节点值importjava.util.ArrayList;importjava.util.Queue;importjava.util.LinkedList;publicclassSolutionpublicArrayList<Integer>PrintFro... 查看详情
java实习生每日10道面试题打卡！(代码片段)
...f0c;有限的时间，尽可能多学一些总没坏处！1、满二叉树、完全二叉树、平衡二叉树、红黑树、二叉搜索树的区别？参考文章：树、二叉树(完全二叉树、满二叉树)概念图解①满二叉树高度为h，由2^h-1个节点构... 查看详情
微软面试题：leetcode543.二叉树的直径出现次数：3(代码片段)
题目描述： 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。分析： 本题和 124.二叉树中的最大路径和 是一样的... 查看详情