5030-节点与其祖先之间的最大差值_Node.js

上一篇: Ghost 基于Node.js的开源博客系统下一篇:使用node打造自己的命令行

5030-节点与其祖先之间的最大差值

发布时间：2019-06-11 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了5030-节点与其祖先之间的最大差值，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

前言
Weekly Contest 132的 节点与其祖先之间的最大差值：

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例：


      
      
      
      
      
输入：[8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
提示：

树中的节点数在 2 到 5000 之间。
每个节点的值介于 0 到 100000 之间。


解题思路
本题需要将问题分解一下，首先先实现根节点与每个节点的差值的最大值的算法，然后只需要遍历每个子树即可。
实现代码

      
      
      node=queue.poll();
            max=Math.max(max,getMaxDiffByRoot(node));
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        return max;
    }

    /**
     * 获取某个根节点下所有节点与根节点的差值的最大值
     * 这里选择使用层序遍历
     * @param root
     * @return
     */
    private int getMaxDiffByRoot(TreeNode root){
        Queue queue = new LinkedList<>();
        queue.add(root);
        //根节点的值，用于比较
        int rootValue=root.val;
        //最大差值
        int max=0;
        while(!queue.isEmpty()){//层序遍历每个节点
            TreeNode node=queue.poll();
            // 获取最大值
            max=Math.max(max,Math.abs(node.val-rootValue));
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        return max;
    }" title="" data-original-title="复制">
      
      
   /**
     * 5030. 节点与其祖先之间的最大差值
     * @param root
     * @return
     */
    public int maxAncestorDiff(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int max=0;
        while(!queue.isEmpty()){//层序遍历
            TreeNode node=queue.poll();
            max=Math.max(max,getMaxDiffByRoot(node));
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        return max;
    }

    /**
     * 获取某个根节点下所有节点与根节点的差值的最大值
     * 这里选择使用层序遍历
     * @param root
     * @return
     */
    private int getMaxDiffByRoot(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //根节点的值，用于比较
        int rootValue=root.val;
        //最大差值
        int max=0;
        while(!queue.isEmpty()){//层序遍历每个节点
            TreeNode node=queue.poll();
            // 获取最大值
            max=Math.max(max,Math.abs(node.val-rootValue));
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        return max;
    }