在本文中，我们将为您详细介绍剑指offer第二版面试题7：二叉树的下一个节点的相关知识，并且为您解答关于JAVA版本的疑问，此外，我们还会提供一些关于LeetCode剑指Offer面试题27.二叉树的
在本文中，我们将为您详细介绍剑指offer第二版面试题7：二叉树的下一个节点的相关知识，并且为您解答关于JAVA版本的疑问，此外，我们还会提供一些关于LeetCode 剑指Offer 面试题27. 二叉树的镜像、[剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树、《剑指Offer》-004 -Java版二叉树先序和中序遍历返回原二叉树、《剑指offer》面试题18 树的子结构 Java版的有用信息。
本文目录一览：- 剑指offer第二版面试题7：二叉树的下一个节点（JAVA版本）（java 二叉树 面试）
- LeetCode 剑指Offer 面试题27. 二叉树的镜像
- [剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树
- 《剑指Offer》-004 -Java版二叉树先序和中序遍历返回原二叉树
- 《剑指offer》面试题18 树的子结构 Java版
剑指offer第二版面试题7：二叉树的下一个节点（JAVA版本）（java 二叉树 面试）
题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析：
根据中序遍历的特点，要找到一个节点的下一个节点无非就是三种情况：
1、有右子树，这时只需要把其右孩子作为下一个遍历的（并不是要找的）节点，然后沿着该节点的左子树（如果有的话）出发，直到遇到叶子节点，那么该叶子节点就是其下一个要找的节点；
2、没有右子树，则判断该节点是否是其父节点的左孩子，如果是则其下一个要找的节点是其父节点；
3、如果不是其父节点的左孩子，则把其父节点作为下一个遍历的节点，向上回溯，直到找到节点没有父节点或者节点是其父节点的左孩子为止。
综合这三种情况就可以找到二叉树中任意一个节点的下一个节点。
代码如下:
public class FindNextNode {
public BinaryTreeNode getNextNode(BinaryTreeNode pNode){
if(pNode==null){
return null;
}
//如果该节点有右节点
if(pNode.getRightNode()!=null){
BinaryTreeNode tempNode=pNode.getRightNode();
while(tempNode.getLeftNode()!=null){
tempNode=tempNode.getLeftNode();
}
return tempNode;
}
//如果没有右节点，是其父节点的左子节点
if(pNode.getFatherNode()==null){
return null;
}
if(pNode.getFatherNode().getLeftNode()==pNode){
return pNode.getFatherNode();
}
//如果没有右节点，是其父节点的右子节点，一直向上找父节点直到没有父节点
if(pNode.getFatherNode()==null){
return null;
}
if(pNode.getFatherNode().getRightNode()==pNode){
BinaryTreeNode tempNode=pNode.getFatherNode();
while(tempNode.getFatherNode()==null){
tempNode=tempNode.getFatherNode();
}
return tempNode;
}
return null;
}
}
LeetCode 剑指Offer 面试题27. 二叉树的镜像
文章目录
- 一、面试题27. 二叉树的镜像
- 二、解题
-
- （一）非递归方式
- （二）递归方式
- 三、小郑有话说
一、面试题27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
二、解题
这个题很直白的就是反转二叉树
（一）非递归方式
package tree.二叉树的镜像;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* @Auther: truedei
* @Date: 2020 /20-6-10
* @Description: 二叉树镜像
*/
public class Solution {
static public TreeNode mirrorTree(TreeNode root) {
if(root==null)
return null;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode gen = new TreeNode(root.val);
while (!queue.isEmpty()){
//交换位置
TreeNode node = queue.pop();
TreeNode temp = node.left;
node.left= node.right;
node.right = temp;
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
return root;
}
public static void main(String[] args) {
TreeNode t1 = new TreeNode(4);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(7);
TreeNode t4 = new TreeNode(1);
TreeNode t5 = new TreeNode(3);
TreeNode t6 = new TreeNode(6);
TreeNode t7 = new TreeNode(9);
t1.left=t2;
t1.right=t3;
t2.left=t4;
t2.right=t5;
t3.left=t6;
t3.right=t7;
TreeNode treeNode = mirrorTree(t1);
}
}
class TreeNode {
int val;//每个节点存放的数据
TreeNode left;//左节点
TreeNode right;//右节点
TreeNode(int x) {
val = x; }
}
（二）递归方式
public TreeNode mirrorTree(TreeNode root) {
//根节点为null时，返回null
if(root==null)
return null;
//当只有根节点时，直接返回
if(root!=null && root.left==null && root.right==null)
return root;
//交换位置
TreeNode temp = root.left;
root.left=root.right;
root.right=temp;
if(root.left!=null)
mirrorTree(root.left);
if(root.right!=null)
mirrorTree(root.right);
return root;
}
三、小郑有话说
如果对你有帮助，可以分享给你身边的朋友。或者
给俺点个大大的赞和大大的评论，点赞和评论就是给我最大的支持，感谢。
水平有限，难免会有疏漏或者书写不合理的地方，欢迎交流讨论。
作者：TrueDei
作者唯一博客ＣＳＤＮ：https://truedei.blog.csdn.net/
转载说明：如需转载请注明原地址和作者名。
如果喜欢我的文章，还没看够可以关注我，我会用心写好每一篇文章。
欢迎大佬们加入在下的小社，在此大家可以放开的交流，共同学习进步：
客官、点个赞再走吧
本文分享 CSDN - TrueDei。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
![[剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树](http://www.gvkun.com/zb_users/upload/2025/02/97d32c16-a5fb-48c8-8fe1-92c560a330e31738551521347.jpg "[剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树")
[剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树
###题目一 ####题目 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 ####题解 递归。 ####代码
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Main {
public int TreeDepth(TreeNode root) {
if(root==null) {
return 0;
}
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
}
###题目二 ####题目 判断二叉树是不是平衡二叉树。注意，此处定义的平衡二叉树：递归地，左右两个子树相差<=1。而不需要二叉搜索树条件。 ####题解 后序遍历，返回值包含是否平衡和当前子树高度。每个节点只需遍历一遍。 ####代码
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
class ReturnType{
boolean balanceTag;
int deepth;
ReturnType(boolean balanceTag,int deepth){
this.balanceTag=balanceTag;
this.deepth=deepth;
}
}
public class Main {
public static void main(String[] args) {
//test case
TreeNode node1=new TreeNode(1);
TreeNode node2=new TreeNode(2);
TreeNode node3=new TreeNode(3);
TreeNode node4=new TreeNode(4);
TreeNode node5=new TreeNode(5);
node1.left=node2;
node1.right=node3;
node2.left=node4;
node4.left=node5;
System.out.println(isBalanced(node1).balanceTag);
}
public static ReturnType isBalanced(TreeNode root){
if(root==null) {
return new ReturnType(true,0);
}
ReturnType r1=isBalanced(root.left);
ReturnType r2=isBalanced(root.right);
int dif=Math.abs(r1.deepth-r2.deepth);
int deepth=Math.max(r1.deepth, r2.deepth)+1;
if(r1.balanceTag&&r2.balanceTag&&dif<=1) {
return new ReturnType(true,deepth);
}
return new ReturnType(false,deepth);
}
}
《剑指Offer》-004 -Java版二叉树先序和中序遍历返回原二叉树
如题 (总结要点)
-
- 注意空值
-
- 假定数据是没有问题的
-
- 前序(根左右) ,中序(左根右), 故每次的第一个节点就是根节点
-
- 没用数组的库函数,自己手写了两个方法
-
- 用Java代码写二叉树很舒服, 没有啥指针,直接赋值就行了!毕竟Java除了基本数据类型传参是形参, 其余都是实参传递.
- 原文链接 : https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
借鉴学习文章列表
- 链接1:
- 链接2:
-
ALiBaBaJavaCodingGuideLines有话说 :
1.题目
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
2. Solution代码
/**
* FileName: ${FILENAME}
* 类的详细说明 : 1. 注意空值
* 2. 假定数据是没有问题的
* 3.前序(根左右) ,中序(左根右), 故每次的第一个节点就是根节点
* @author SongZeShan
* @version 1.0
* @Date 2019/7/11 18:10
*/
public class Solution {
/**重建出该二叉树*/
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0||pre.length!=in.length){
return null;
}
//建树,根节点赋值
TreeNode treeNode = new TreeNode(pre[0]);
int index = indexOf(in,pre[0]);
//左子树长度为index-1
treeNode.left = reConstructBinaryTree(copyRange(pre, 1, index), copyRange(in, 0, index-1));
//右子树为长度为in.length-index
treeNode.right = reConstructBinaryTree(copyRange(pre, index+1, pre.length-1), copyRange(in, index+1, pre.length-1));
return treeNode;
}
/**复制下标*/
private int[] copyRange(int arr[],int beg,int end){
int []newArr = new int[end-beg+1];
for(int i=beg;i<=end;i++){
newArr[i-beg]=arr[i];
}
return newArr;
}
/**查找key值,返回索引index*/
private int indexOf(int []arr,int key){
for(int i=0;i<arr.length;i++){
if(key==arr[i]){
return i;
}
}
return -1;
}
}
3.TreeNode 二叉树代码
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
4.测试
/**
* FileName: ${FILENAME}
* 类的详细说明
*
* @author SongZeShan
* @version 1.0
* @Date 2019/7/11 18:10
*/
public class Test {
public static void main(String[] args) {
Solution solution = new Solution();
int pre[] = {1,2,4,7,3,5,6,8};
int in[] = {4,7,2,1,5,3,8,6};
TreeNode treeNode = solution.reConstructBinaryTree(pre,in );
//输出测试
preOrder(treeNode);
System.out.println();
midOrder(treeNode);
}
/**遍历一次二叉树先序输出*/
private static void preOrder(TreeNode node){
if(node==null){
return ;
}
System.out.print(node.val+"\t");
preOrder(node.left);
preOrder(node.right);
}
/**遍历一次二叉树中序输出*/
private static void midOrder(TreeNode node){
if(node==null){
return ;
}
midOrder(node.left);
System.out.print(node.val+"\t");
midOrder(node.right);
}
}
测试结果 ,和原答案一模一样
1 2 4 7 3 5 6 8
4 7 2 1 5 3 8 6
Process finished with exit code 0
《剑指offer》面试题18 树的子结构 Java版
（输入两棵二叉树A和B，判断B是不是A的子结构。补充下，根据书中的代码来看，子结构的定义并不包括叶子节点下的null，也就是说只要B的存在数字的结构存在于A中就行，那么如果B是null树，那么就不属于A的子结构）
书中方法：书上的方法十分清晰，分为两个步骤，先在A树中找到B树的root.val，然后判断由该点向下是否完全包含B树的结构，直至遍历完A树。
public boolean isChild(TreeNode aRoot, TreeNode bRoot){
//A树没有遍历完而且B树不为空
if(aRoot != null && bRoot != null){
//在当前节点检查结构，或者去遍历当前节点的左节点或右节点。
return isQualified(aRoot, bRoot)
|| isChild(aRoot.left, bRoot)
|| isChild(aRoot.right, bRoot);
}
//A树遍历完了或者B树是个null
return false;
}
private boolean isQualified(TreeNode aRoot, TreeNode bRoot){
//检查到了B的末尾
if(bRoot == null)return true;
//如果在检查完B之前A到了底
if(aRoot == null)return false;
//都不是null且val相等，继续检查
if(aRoot.val == bRoot.val){
return isQualified(aRoot.left, bRoot.left)
&& isQualified(aRoot.right, bRoot.right);
}
//都不是null但是val不等
return false;
}
我的方法：开始检查一下B是否为空，空的话返回false（定义）。aRoot和bRoot是两个根节点，且都可能在自己的根节点和子节点之间转换。开头，如果aRoot.val和bRoot.val相等了，那么继续对各自的子节点进行对比；如果不相等则移动aRoot并和bRoot进行比较。
public boolean isChildTree(TreeNode aRoot, TreeNode bRoot){
//定义，如果B树为空，返回false
if(bRoot == null){
return false;
}
return isChild2(aRoot, bRoot);
}
private boolean isChild2(TreeNode aRoot, TreeNode bRoot){
//如果检查到了B的末尾
if(bRoot == null)return true;
//A到了末尾但是B没有
if(aRoot == null)return false;
//如果当前节点相同，进行进一步对比；
//对比的结果可能是false，此时继续向下检查aRoot.left与bRoot、aRoot.right与bRoot
if(aRoot.val == bRoot.val){
return (isChild2(aRoot.left, bRoot.left) && isChild2(aRoot.right, bRoot.right))
|| isChild2(aRoot.left, bRoot)
|| isChild2(aRoot.right, bRoot);
}else{//如果当前节点不同，继续向下检查aRoot.left与bRoot、aRoot.right与bRoot
return isChild2(aRoot.left, bRoot)
|| isChild2(aRoot.right, bRoot);
}
}
关于剑指offer第二版面试题7：二叉树的下一个节点和JAVA版本的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于LeetCode 剑指Offer 面试题27. 二叉树的镜像、[剑指Offer]55-题目一：二叉树的深度 题目二：平衡二叉树、《剑指Offer》-004 -Java版二叉树先序和中序遍历返回原二叉树、《剑指offer》面试题18 树的子结构 Java版等相关知识的信息别忘了在本站进行查找喔。
本文标签：
