小挑战
本专题带大家认识二叉树的数据结构，二叉树在一种常用的数据结构，掌握二叉树对我们的技术学习多有裨益！
题目1
请你将二叉树分别按照前序遍历，中序遍历，后序遍历的方式输出各节点的值。
题目2
请你将二叉树各节点的值，按层输出，层序遍历
public class Node{
Node left;
Node right;
int value;
public Node(int value){
this.value = value;
}
}
public static List<List<Integer>> levelOrder(Node node){
}
题目3
给你两棵树，请你判断两个树的结构是否相同
题目4
给你一棵树，请你判断该树是否是镜面树
题目5
给你一棵树，请你返回树的最大深度
题目6
给你一棵树，请你判断该树是否是平衡二叉树
题目7
给你一棵树，请你判断该树是否是搜索二叉树
题目8
给你一棵树按照前序遍历以及中序遍历后的数组，请你组装树，并返回头结点
题目9
给你指一棵二叉树，请你判断该树从头结点到叶子节点是否存在指定数值的路径和？
题目10
给你指一棵二叉树，以及指定路径和，请你返回该树从头结点到叶子节点满足该路径和的全部路径？
---------------------- 我是优美的分割线----------------------
题目1
请你将二叉树分别按照前序遍历，中序遍历，后序遍历的方式输出各节点的值。
参考题解
public class Node{
Node left;
Node right;
int value;
public Node(int value){
this.value = value;
}
}
public static void preorder(Node node){
if(node == null){
return;
}
System.out.print(node.value + " ");
preorder(node.left);
preorder(node.right);
}
public static void inorder(Node node){
if(node == null){
return;
}
inorder(node.left);
System.out.print(node.value + " ");
inorder(node.right);
}
public static void posorder(Node node){
if(node == null){
return;
}
posorder(node.left);
posorder(node.right);
System.out.print(node.value + " ");
}
TIPS
前序遍历：各节点按照 根节点，左子树，右子树的顺序遍历。
中序遍历：各节点按照 左子树，根节点，右子树的顺序遍历。
后序遍历：各节点按照 左子树，右子树，根节点的顺序遍历。
题目2
请你将二叉树各节点的值，按层输出，层内按照左到右的顺序；层序遍历
参考题解：
public class Node{
Node left;
Node right;
int value;
public Node(int value){
this.value = value;
}
}
public static List<List<Integer>> levelOrder(Node node){
List<List<Integer>> res = new LinkedList<>();
if (node == null) {
return res;
}
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> cur = new LinkedList<>();
for(int i=0;i<size;i++){
Node curNode = queue.poll();
cur.add(curNode.value);
if(curNode.left!=null){
queue.add(curNode.left);
}
if(curNode.right!=null){
queue.add(curNode.right);
}
}
res.add(cur);
}
return res;
}
TIPS
可以利用队列先进先出的特性，依次入队根节点，输出；
然后入队左节点，入队右节点；再依次输出的过程。
题目3
给你两棵树，请你判断两个树的结构是否相同
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static boolean isSameTree(Node node1, Node node2) {
if(node1 == null && node2 == null){
return true;
}
if(node1 == null ^ node2 == null){
return false;
}
return node1.value==node2.value
&&isSameTree(node1.left,node2.left)
&&isSameTree(node1.right,node2.right);
}
TIPS
两个树结构是否相同要求：
从根节点开始，
两棵树左子树完全相同；
两棵树右子树完全相同。
题目4
给你一棵树，请你判断该树是否是镜面树
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static boolean isMirrorTree(Node node1) {
checkMirror(node1, node1);
}
public static boolean checkMirror(Node node1, Node node2) {
if(node1 == null && node2 == null){
return true;
}
if(node1 == null ^ node2 == null){
return false;
}
return node1.value==node2.value
&&checkMirror(node1.left,node2.right)
&&checkMirror(node1.right,node2.left);
}
TIPS
镜面树结构要求是：
左子树的左节点，等于右子树的右节点；
左子树的右节点，等于右子树的左节点。
题目5
给你一棵树，请你返回树的最大深度
参考题解：
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static int deep(Node node){
if(node == null){
return 0;
}
return Math.max(deep(node.left), deep(node.right)) + 1;
}
题目6
给你一棵树，请你判断该树是否是平衡二叉树
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
//自定义辅助类
class NodeInfo{
boolean isBalance;
int deep;
public NodeInfo(boolean isBalance, int deep){
this.deep =deep;
this.isBalance =isBalance;
}
}
public static boolean isBalance(Node node){
return check(node).isBalance;
}
public static NodeInfo check(Node node){
if(node ==null){
return new NodeInfo(true,0);
}
NodeInfo l =check(node.left);
NodeInfo r =check(node.right);
return new NodeInfo(Math.abs(right.deep - left.deep) <= 1
&&l.isBalance&&r.isBalance
, Math.max(l.deep ,r.deep) +1);
}
TIPS
平衡二叉树定义：所有节点的左子树深度与右子树深度相差不超过1
题目7
给你一棵树，请你判断该树是否是搜索二叉树
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
//自定义辅助类
class SearchInfo{
boolean isBST;
int max;
int min;
public SearchInfo(boolean isBST, int min, int max){
this.min =min;
this.max =max;
this.isBST =isBST;
}
}
public static boolean isBST(Node node){
return check(node).isBST;
}
public static SearchInfo check(Node node){
if(node ==null){
return null;
}
int max = node.value;
int min = node.value;
boolean isBST = true;
SearchInfo l=check(node.left);
SearchInfo r=check(node.right);
if(l!=null){
max = Math.max(l.max,max);
min = Math.min(l.min,min);
}
if(r!=null){
max = Math.max(r.max,max);
min = Math.min(r.min,min);
}
boolean lBst = l == null ? true : l.isBST;
boolean rBst = r == null ? true : r.isBST;
boolean lessThan= l==null?true: l.max<node.value;
boolean moreThan= r==null?true: l.min>node.value;
isBST = lBst&&rBst&&lessThan&&moreThan;
return new SearchInfo(isBST, min, max);
}
TIPS
搜索二叉树的定义
所有左子树子节点均小于其父节点
所有右子树子节点均大于其父节点
题目8
给你一棵树按照前序遍历以及中序遍历后的数组，请你组装树，并返回头结点
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static Node buildTree(int[] preorder, int[] inorder){
if(preorder==null || inorder==null
|| preorder.length!=inorder.length){
return null;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
return build(preorder,0,preorder.length-1,
inorder,0,inorder.length-1,map);
}
public static Node build(int[] preorder, int l1, int r1,
int[] inorder, int l2,int r2,Map<Integer,Integer> map ){
if(l1>r1){
return null;
}
Node node= new Node(preorder[l1]);
if(l1 == r1){
return node;
}
int h = map.get(preorder[l1]);
node.left=build(preorder,l1+1,h-l2,inorder,l2,h-1,map);
node.right=build(preorder,h-l2+1,r1,inorder,h+1,r2,map);
return node;
}
题目9
给你指一棵二叉树，请你判断该树从头结点到叶子节点是否存在指定数值的路径和？
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static boolean flag =false;
public static boolean containsPath(Node node,int sum){
flag =false;
check(node,0,sum);
return flag;
}
public static void check(Node node,int pre,int sum){
if(node ==null || flag){
return;
}
if(node.left==null&&node.right==null){
if(sum-pre = node.value){
flag = true;
}
return;
}
if(node.left!=null){
check(node.left,pre+node.value,sum);
}
if(node.right!=null){
check(node.right,pre+node.value,sum);
}
}
题目10
给你指一棵二叉树，以及指定路径和，请你返回该树从头结点到叶子节点满足该路径和的全部路径？
参考题解
class Node {
int value;
Node right;
Node left;
public Node(int value) {
this.value = value;
}
}
public static List<List<Integer>> pathSum(Node root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
handlePath(root, 0, targetSum, path, res);
return res;
}
public static void handlePath(Node node, int pre, int total, List<Integer> path, List<List<Integer>> res) {
if (node == null) {
return;
}
//判断是叶子节点
if (node.right == null && node.left == null) {
if (total - pre == node.value) {
path.add(node.value);
List<Integer> cur = copy(path);
res.add(cur);
path.remove(path.size() - 1);
}
}
path.add(node.value);
if (node.left != null) {
handlePath(node.left, pre + node.value, total, path, res);
}
if (node.right != null) {
handlePath(node.right, pre + node.value, total, path, res);
}
path.remove(path.size() - 1);
}
public static List<Integer> copy(List<Integer> list) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
result.add(list.get(i));
}
return result;
}
- 本文链接： https://www.sunce.wang/archives/suan-fa-xiao-lian-xi-zhi-er-cha-shu-zhuan-ti
- 版权声明： 本博客所有文章除特别声明外，均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处！