Find the Maximum Difference Between a Node and Its Ancestor in Java

2025年5月10日 | 阅读 4 分钟

在二叉树中，节点与其祖先之间的最大差值是指将一个后代节点的值减去其某个祖先节点的值所能达到的最大值。节点的祖先是指从根到该节点路径上的任何节点，不包括该节点本身。

这个问题通常通过递归来解决，我们在遍历树时，会跟踪以每个节点为根的子树中存在的最小值。在每一步，都会计算当前节点的值与最小后代值之间的差值，并根据需要调整迄今为止遇到的最大差值。

示例 1

输入

二叉树

 
        8  
       / \  
      3   10  
     / \    \  
    1   6    14  
       / \   /  
      4   7 13     

输出

 
Maximum difference between an ancestor and a node is: 7

解释

最大差值计算为 (节点 8 - 节点 1) = 7。
树中没有其他祖先-节点对可以产生更大的差值。

示例 2

输入

二叉树

 
        15  
       /   \  
      10    20  
     / \      \  
    5   12     25  
   /      \  
  1        13     

输出

 
Maximum difference between an ancestor and a node is: 14

解释

最大差值为 (节点 15 - 节点 1) = 14。这是给定树中最大的祖先-节点差值。

算法

步骤 1：通过生成单独的节点并将它们链接起来形成具有定义的父子连接的层次结构，创建一个二叉树。

步骤 2：开发一个递归函数，使用深度优先方法来探索树，同时跟踪在每个子树中遇到的最小值。

步骤 3：在每个节点，确定其值与在其后代节点中找到的最低值之间的绝对差值，以评估可能的差值。

步骤 4：使用一个全局变量来记录在整个遍历过程中找到的最大差值，确保在找到更大的值时进行更新。

步骤 5：一旦遍历完整个树，就返回记录的最大差值作为最终输出，这代表了给定二叉树中最大的祖先-节点差值。

让我们在 Java 程序中实现上述步骤。

class TreeNode {
    int value; // Stores the value of the node
    TreeNode left, right; // References to left and right child nodes
    // Constructor to initialize the node with a given value
    public TreeNode(int value) {
        this.value = value; // Assigns the provided value to the node
        left = right = null; // Initializes left and right children as null
    }
}
class Result {
    int maxDifference = Integer.MIN_VALUE; // Stores the maximum difference found between an ancestor and a node
}
public class MaxAncestorDifference {
    TreeNode root; // Root node of the binary tree
    // Recursive function to compute the maximum difference between an ancestor and a node
    private int findMaxDifference(TreeNode node, Result result) {
        if (node == null) { // Base case: if the node is null
            return Integer.MAX_VALUE;
        }
        if (node.left == null && node.right == null) {
            return node.value; // Return its value since it has no descendants
        }
        // Recursively find the minimum value in the left and right subtrees
        int minValue = Math.min(findMaxDifference(node.left, result),
                                findMaxDifference(node.right, result));
        result.maxDifference = Math.max(result.maxDifference, node.value - minValue);
        // Return the minimum value found in the subtree (to be used by its ancestor)
        return Math.min(minValue, node.value);
    }
    // Wrapper function to start the max difference calculation from the root
    public int getMaxDifference(TreeNode root) {
        Result result = new Result(); // Create an instance of Result to store the maximum difference
        findMaxDifference(root, result); // Call the recursive function to compute the maximum difference
        return result.maxDifference; // Return the computed maximum difference
    }
    public static void main(String[] args) {
        MaxAncestorDifference tree = new MaxAncestorDifference();
        // Constructing the binary tree
        tree.root = new TreeNode(8); 
        tree.root.left = new TreeNode(3); 
        tree.root.left.left = new TreeNode(1); 
        tree.root.left.right = new TreeNode(6); 
        tree.root.left.right.left = new TreeNode(4); 
        tree.root.left.right.right = new TreeNode(7); 
        tree.root.right = new TreeNode(10); 
        tree.root.right.right = new TreeNode(14); 
        tree.root.right.right.left = new TreeNode(13);
        // Compute and print the maximum difference between an ancestor and a node
        int maxDiff = tree.getMaxDifference(tree.root); // Call the function to compute max difference
        System.out.println("Maximum difference between an ancestor and a node is: " + maxDiff); // Display result
    }
}

输出

 
Maximum difference between an ancestor and a node is: 7

时间复杂度：O(N)，因为在遍历过程中每个节点都被访问一次。

辅助空间：O(H)，由于递归堆栈的使用，其中 H 是树的高度。

下一个主题Java 元组

Find the Maximum Difference Between a Node and Its Ancestor in Java

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Find the Maximum Difference Between a Node and Its Ancestor in Java

算法

相关帖子

Java 15 特性

Java 程序在不使用额外空间的情况下合并两个数组

Labeled Loop in Java

Mobile Number Validation in Java

Identifiers in Java

Java 中 Vector 和 Array 的区别

Java 中锯齿形星形和数字图案

DecimalFormat getMinimumIntegerDigits() method in Java

Java 中 HashSet 的各种操作

Design of JDBC

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器