【LeetCode】剑指 Offer 08. 二叉树的下一个节点 p65 -- Java Version

题目链接：无题目链接，不知道为啥力扣上找不到这一题。

1. 题目介绍（08. 二叉树的下一个节点）

题目：给定一个二叉树和其中的一个节点，请找出中序遍历顺序的下一个节点并且返回。注意，树中的节点除了有两个分别指向左、右子节点的指针，还要一个指向父节点的指针。

【测试用例】：
示例1：（一颗有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的指针用虚线表示）

中序遍历序列 {d,b,h,e,i,a,f,c,g}

• a的下一节点为f
• b的下一节点为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. 思考

找中序遍历二叉树的下一个节点，主要就分为三种情况：

1. 当前节点有右子树，那么Next就是其右子树的最左子节点；
2. 当前节点无右子树，如果该节点是父节点的左子节点，那么Next就是其父节点；
3. 当前节点无右子树，如果该节点是父节点的右子节点，那么从其父节点开始向上查找，直到找到其父节点是左子节点的父节点，那么Next就是该父节点。

4. 可参考资料

[1] 大神整理的剑指Offer【所有面试题汇总】
[2] 【剑指Offer学习】【面试题58：二叉树的下一个结点】（代码结构参考）