四川省建设厅网站首页,网站架构策划,双控机制建设网站,做网站刷QQ会员网站题目链接#xff1a;无题目链接#xff0c;不知道为啥力扣上找不到这一题。
1. 题目介绍#xff08;08. 二叉树的下一个节点#xff09; 题目#xff1a;给定一个二叉树和其中的一个节点#xff0c;请找出中序遍历顺序的下一个节点并且返回。注意#xff0c;树中的节点…题目链接无题目链接不知道为啥力扣上找不到这一题。
1. 题目介绍08. 二叉树的下一个节点 题目给定一个二叉树和其中的一个节点请找出中序遍历顺序的下一个节点并且返回。注意树中的节点除了有两个分别指向左、右子节点的指针还要一个指向父节点的指针。 【测试用例】 示例1一颗有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示从子节点指向父节点的指针用虚线表示 中序遍历序列 {d,b,h,e,i,a,f,c,g} a的下一节点为fb的下一节点为h 2. 题解
2.1 讨论3种情况 – O(n)
package com.thomas.offer;public class Offer08_BinaryTreeNext {// 定义二叉树节点结构public static class TreeNode {private String val;private TreeNode left;private TreeNode right;private TreeNode parent;public TreeNode(String val) {this.val val;}Overridepublic String toString() {return val ;}}/*3种情况1. 当前节点有右子树那么Next就是其右子树的最左子节点2. 当前节点无右子树如果该节点是父节点的左子节点那么Next就是其父节点3. 当前节点无右子树如果该节点是父节点的右子节点那么从其父节点开始向上查找直到找到其父节点是左子节点的父节点那么Next就是该父节点* */public static TreeNode nextNode(TreeNode node) {// 1. 判空操作if (node null) return null;// 2. 第一种情况节点有右子树Next为其右子树的最左子节点if (node.right ! null) {node node.right;while (node.left ! null) {node node.left;}return node;}// 3. 第二种情况节点无右子树且该节点为其父节点的左子节点Next为其父节点if (node node.parent.left) return node.parent;// 4. 第三种情况节点无右子树且该节点为其父节点的右子节点Next是一个父节点 Xxx父节点是该父节点的左子节点if (node node.parent.right) {// 循环结束条件node node.parent.left,// 即找到了其父节点是左子节点的父节点node node.parent;while (node ! node.parent.left) {node node.parent;// 注意最右节点也属于该情况但它无法满足循环结束条件在这里我们判断一下返回null即可if (node.parent null) {return null;}}return node.parent;}return null;}// 建树public static void createTree(TreeNode node,TreeNode left,TreeNode right,TreeNode parent) {node.left left;node.right right;node.parent parent;}public static void main(String[] args) {// 1。 创建二叉树节点对象TreeNode a new TreeNode(a);TreeNode b new TreeNode(b);TreeNode c new TreeNode(c);TreeNode d new TreeNode(d);TreeNode e new TreeNode(e);TreeNode f new TreeNode(f);TreeNode g new TreeNode(g);TreeNode h new TreeNode(h);TreeNode i new TreeNode(i);// 二叉树中序遍历 {d,b,h,e,i,a,f,c,g}// 2. 构造二叉树createTree(a, b, c, null);createTree(b, d, e, a);createTree(c, f, g, a);createTree(d, null, null, b);createTree(e, h, i, b);createTree(f, null, null, c);createTree(g, null, null, c);createTree(h, null, null, e);createTree(i, null, null, e);// 3. 调用nextNode方法打印结果System.out.println(nextNode(a)); // fSystem.out.println(nextNode(b)); // hSystem.out.println(nextNode(c)); // gSystem.out.println(nextNode(d)); // bSystem.out.println(nextNode(e)); // iSystem.out.println(nextNode(f)); // cSystem.out.println(nextNode(g)); // nullSystem.out.println(nextNode(h)); // eSystem.out.println(nextNode(i)); // a}} 3. 思考
找中序遍历二叉树的下一个节点主要就分为三种情况
当前节点有右子树那么Next就是其右子树的最左子节点当前节点无右子树如果该节点是父节点的左子节点那么Next就是其父节点当前节点无右子树如果该节点是父节点的右子节点那么从其父节点开始向上查找直到找到其父节点是左子节点的父节点那么Next就是该父节点。
4. 可参考资料
[1] 大神整理的剑指Offer【所有面试题汇总】 [2] 【剑指Offer学习】【面试题58二叉树的下一个结点】代码结构参考
