二叉树算法—后继节点

与其明天开始，不如现在行动！

文章目录

- 1 后继节点
- - 1.1 解题思路
  - 1.2 代码实现
💎总结

1 后继节点

在这里插入图片描述

1.1 解题思路

二叉树节点结构定义如下：

public static class Node {
public int cal;
public Node left;
public Node right;
public Node parent;
}
给你二叉树中的某个节点，返回该节点的后继节点

后继节点就是二叉树中序遍历，这个节点的下一个节点

思路

如果该节点有右子树，那么后继节点就是右树的最左节点
如果该节点没有右子树
1. 如果该节点是父节点的左节点，此时父节点就是后继节点
2. 如果该节点是父节点的右节点，向上寻找
  1. 这个节点在顶部节点的右树上，此时返回的是空
  2. 如果这个节点在某个节点的左数上，返回此时的节点

1.2 代码实现

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 node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        }else{
            Node cur = node;
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                cur = parent;
                parent = cur.parent;
            }
            return parent;
        }
    }

    private static Node getLeftMost(Node node) {
        Node cur = node;
        if (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }
    
    // 测试
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n2.parent = n1;
        n3.left = n6;
        n3.right = n7;
        n3.parent = n1;
        n4.parent = n2;
        n5.parent = n2;
        n6.parent = n3;
        n7.parent = n3;

        System.out.println(getSuccessorNode(n6).val);
    }
}