在二叉树中找到一个节点的后继节点-白红宇

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

阅读量：4166 次

发布时间：2019-05-26

本文共 3104 字，大约阅读时间需要 10 分钟。

二叉树中一个节点的后继节点指的是，二叉树的中序遍历的序列中的下一个节点。

链接：https://www.nowcoder.com/questionTerminal/c37ec6a9e4084b9c943be2d3a369e177
来源：牛客网

输入描述: 第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行四个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa
没有左儿子，rch同理)

最后一行输入要询问的节点 node。

输出描述: 输出一个整数表示答案。(如果 node 是最后一个节点，则输出 0 ) 示例1 输入
10 6
6 3 9
3 1 4
1 0 2
2 0 0
4 0 5
5 0 0
9 8 10
10 0 0
8 7 0
7 0 0
10
输出 0

import java.util.HashMap;import java.util.Map;import java.util.Scanner;public class Main {
       public static void main(String[] args) {
           Map
   
     map = new HashMap<>();        Map
    
      parent = new HashMap<>();        /**         * 读取数据         */        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        TreeNode root = new TreeNode(scanner.nextInt());        map.put(root.val, root);        scanner.nextLine();        for (int i = 0; i < n; i++) {
               int val = scanner.nextInt();            TreeNode node;            if (!map.containsKey(val)) {
                   node = new TreeNode(val);                map.put(node.val, node);            } else {
                   node = map.get(val);            }            int left = scanner.nextInt();            if (left != 0) {
                   node.left = new TreeNode(left);                map.put(left, node.left);                parent.put(left, node);            } else {
                   node.left = null;            }            int right = scanner.nextInt();            if (right != 0) {
                   node.right = new TreeNode(right);                map.put(node.right.val, node.right);                parent.put(right, node);            } else {
                   node.right = null;            }            node.parent = parent.get(node.val);        }        Integer target = scanner.nextInt();        /**         * 找到 target 的下一个节点         */        int result = 0;        TreeNode node = map.get(target);        if (node.right != null) {
               // target有右子树：下一个节点就是右子树的最左节点            node = node.right;            while (node.left != null) {
                   node = node.left;            }            result = node.val;        } else if (node.parent.left == node) {
               // target没有右子树 且 target是其父节点的左子树：后继节点就是target的父节点            result = node.parent.val;        } else {
               // target没有右子树 且 target是其父节点的右子树：找到第一个使target在左子树的祖先节点            node = node.parent;            while (node.parent != null && node != node.parent.left) {
                   node = node.parent;            }            result = node.parent.val;            // target是最后一个节点            if (node.parent == root) {
                   result = 0;            }        }        System.out.println(result);    }}class TreeNode {
       int val;    TreeNode left;    TreeNode right;    TreeNode parent;    public TreeNode(int val) {
           this.val = val;    }    @Override    public String toString() {
           return "TreeNode{" +                "val=" + val +                ", left=" + left +                ", right=" + right +                "}\n";    }}