算法学习之常见的二叉树算法题

常见二叉树算法题

后继节点

在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。

现在有一种新的二叉树节点类型如下：

public static 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的后继节点的函数。

public static Node getSuccessorNode(Node node){
    if(node == null)
        return node;

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

主要有两种情况
1)如果node节点有右子树，后继节点则为右子树的最左节点
2)如果node节点无右子树，则node为后继节点左子树的最右节点

打赏