HOME/剑指Offer/

在二叉树中找到一个节点的后继节点

Article Outline
TOC
Collection Outline

在二叉树中找到一个节点的后继节点

【题目】 现在有一种新的二叉树节点类型如下:

public class Node { 
    public int value; 
    public Node left;
    public Node right; 
    public Node parent;
    public Node(int data) { 
        this.value = data; 
    }
}

该结构比普通二叉树节点结构多了一个指向父节点的 parent 指针。假设有一 棵 Node 类型的节点组成的二叉树,树中每个节点的 parent 指针都正确地指向自己的父节点,头节点的 parent 指向 null。只给一个在二叉树中的某个节点 node,请实现返回 node 的后继节点的函数。

【概念】==在二叉树中,前驱结点和后继结点是按照二叉树中两个结点被中序遍历的先后顺序来划分的==。以下面的树形结构为例,中序遍历结果为:4 2 5 1 6 3 7,则 1 的后继结点为 6,前驱结点为 5

二叉树结构

【解答】

  • 一般方法:可以通过给定结点的 parent 指针一直找到根结点,然后从根节点中序遍历整个树,在遍历到该结点的时候标记一下,那么下一个要打印的结点就是该结点的后继结点。最后根据中序遍历的结果得到每个结点的后继结点;
    • 时间复杂度为:O(N)
  • 改进解法: 例如 5 的后继结点为 1,能不能通过 5 2 1 这样的结构找到,即当前结点距离后继结点的距离长度就是所要的复杂度;
    • 具体方案
      • 如果一个结点有右子树,则后继结点就是其右子树上最左边的结点;例:1 的后继为 6;
      • 如果没有右子树,则使用 parent 指针一直向上找(指向当前结点的指针和 parent 指针同时向上移动),一直到当前指向的结点是当前结点父结点的左孩子就停止,则该父结点就是所求结点的后继结点; 示例图: 题目三寻找后继结点示例 以结点 11 为例,其父结点为 5,11 不是 5 的左结点,向上,5 的父结点为 2,5 不是 2 的左结点,向上,2 是 1 的左结点,则节点 11 的后继结点为 1;

补充:求前驱结点:方案如下: 如果结点有左子树,该结点的前驱就是左子树的最右边结点; 如果结点没有左子树,就一直往上找,直到指向的结点是其父结点的右孩子为止;

package cn.test;

/**
 * @Author smallmartial
 * @Date 2020/3/17
 * @Email [email protected]
 */
public class SuccessorNode {
    public static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int val) {
            this.val = val;
        }
    }

    public static Node getSuccessorNode(Node root) {
        if(root == null){
            return  root;
        }
        //说明当前结点有右子树,则后继结点为右子树的最左结点
        if(root.right != null){
            return getLeftMost(root.right);
        }else {
            //如果没有右子树,则使用 parent 指针一直向上找(指向当前结点的指针和 parent 指针同时向上移动),
            // 一直到当前指向的结点是当前结点父结点的左孩子就停止,则该父结点就是所求结点的后继结点;
            Node parent = root.parent;
            // 当前节点是父结点的左孩子则停止;整棵树最右边的节点是没有后继的,
            // 例如节点7,最终一直上升到节点1,但是节点1的 parent指向null,所有最后返回
            // null表示没有后继;
            while (parent != null && parent.left != root){
               root = parent;
               parent = root.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if(node == null){
            return node;
        }
        while (node.left != null){
            node = node.left;
        }
        return node;
    }

    public static void main(String[] args) {
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;

        Node test = head.left.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.left.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.left.right.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.left.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.left;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right;
        System.out.println(test.val + " next: " + getSuccessorNode(test).val);
        test = head.right.right; // 10's next is null
        System.out.println(test.val + " next: " + getSuccessorNode(test));
    }
}