JZ8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。

输入描述：

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点。

返回值描述：

返回传入的子树根节点的下一个节点，后台会打印输出这个节点。

示例1

输入：

{8,6,10,5,7,9,11},8

返回值：

示例2

输入：

{8,6,10,5,7,9,11},6

返回值：

示例3

输入：

{1,2,#,#,3,#,4},4

返回值：

示例4

输入：

{5},5

返回值：

"null"
// 不存在，后台打印"null"

解析

本题要求寻找输入的二叉树节点在中序遍历中的下一个节点，涉及到了中序遍历的顺序，很容易想到的一个方法是进行一次中序遍历，用数组按顺序保存所有的节点，遍历完后再在数组中寻找输入节点的下一个节点。

代码清单

import java.util.ArrayList;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private ArrayList nodeList = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 传入的是树中的某一节点，需要先找到树的根节点
        TreeLinkNode root = pNode;
        while(root.next!=null)
            root = root.next;
        MidOrder(root);
        for(int i = 0;i


这种方式容易想到，实现也简单，空间复杂度为O(n)，时间复杂度为O(n)。不过要是为了这种简单方式写一篇笔记属实小题大做了，所以还要研究更简单的方法！
考虑中序遍历中下一个节点的问题，以这么一颗二叉树为例，有三种情况

     


当前节点有右孩子，则下一个节点是当前节点右子树中的最左节点。即若当前节点为 B，则下一个节点为 H。
当前节点无右孩子，且自身是父节点的左孩子，则下一个节点是当前节点的父节点。即若当前节点为 H，则下一个节点为 E。
当前节点无右孩子，且自身是父节点的右孩子，说明当前节点是子树中的最后一个节点，需要往上追溯到是某个节点左孩子的祖先节点，下一个节点就是该祖先节点的父节点，若找不到这样的祖先节点，则自身没有下一个节点。即若当前节点为 I，说明 B 子树已经遍历完毕，且祖先节点 B 是其父节点 A 的左孩子，则下一个节点是 A；若当前接地那为 G，说明 C 子树已经遍历完毕，且找不到一个祖先节点是其父节点的左孩子，说明没有下一个节点。

可以看出有两个步骤，第一步是判断自己是否有右孩子，这是由中序遍历左根右的顺序决定的，若有右孩子则需要在右孩子中寻找第一个节点；若没有则进入第二步，判断自己是左孩子还是右孩子，若是左孩子，则根据左根右的顺序，下一个是根，即父节点；若是右孩子，说明当前子树遍历完了（自身是右孩子且自身没有右孩子），需要找到当前遍历完的是左子树还是右子树，若是左子树，则下一个节点是该左子树的父节点，若是右子树，则全部遍历已经完成。
代码清单
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode temp = null;
        // 当前节点有右孩子，下一个节点是右孩子中的最左节点
        if(pNode.right != null){
            // 寻找右孩子的最左节点
            temp = pNode.right;
            while( temp.left != null)
                temp = temp.left;
            return temp;
        }
        // 过了上面说明当前节点无右孩子
        // 自身是父节点的左孩子，则下一个节点是父节点
        if(pNode.next != null && pNode == pNode.next.left)
            return pNode.next;
        // 自身是父节点的右孩子，需要寻找为左子树的祖先节点
        if(pNode.next != null && pNode == pNode.next.right){
            temp = pNode;
            while(temp.next != null){
                if(temp == temp.next.left)
                    return temp.next;
                temp = temp.next;
            }
        }
        return null;
    }
}

这种方式的空间复杂度为O(1)，时间复杂度为O(n)，比之前的方式要好一点。
总结
也没什么好说的，第一种方式记录了全部顺序，比较暴力，第二种方式对中序遍历的情况进行了考量，单独进行三种情况的判断即可！当然从本题树的结构中有父节点的指针可以看出，比较合理的应该也是第二种方式。

JZ8 二叉树的下一个结点

JZ8 二叉树的下一个结点

描述

解析

总结

相关

标签