精华内容
下载资源
问答
  • LeetCode 节点与其祖先之间最大差值 题目: 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。(如果 A 的任何子节点之一为 B,或者 A 的任何子...

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

    题目:
    给定二叉树的根节点 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 得出。

    解题思路:
    1.当给定题目为二叉树相关的时候优先考虑用递归做(几乎都能做出来可能效率上来说也许不是最高)。
    2.那么我们考虑如何求任意一个节点和子节点之间的最大值。
    3.一个节点和子节点之间的最大值必然由以下几个值当中产生:
    当前找到的最大的值和当前节点的差值(因为当前找到的最大的值的节点肯定是当前节点的祖先)
    当前找到的最小的值和当前节点的差值(当前找到的最小的值的节点必然是当前节点的祖先)
    当前找到的最大差值V(取上述三者最大值)
    4.递归操作3,不断更新当前找到的最大的值,当前找到的最小的值,当前找到的最大差值V。
    5.递归结束后,当前找到的最大差值V即为整体的最大差值。

    具体代码实现:

    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int maxAncestorDiff(TreeNode* root) {
            FindCurrentMax(root,root->val,root->val);
            return nMax;
        }
        
        int nMax = 0;
        
        void FindCurrentMax(TreeNode* root,int curMin,int curMax)
        {
            if(!root)
                return;
            if(root->val-curMin>nMax)
                nMax = root->val-curMin;
            if(curMax - root->val>nMax)
                nMax = curMax - root->val;
            if(root->val<curMin)
                curMin = root->val;
            if(root->val>curMax)
                curMax = root->val;
            FindCurrentMax(root->left,curMin,curMax);
            FindCurrentMax(root->right,curMin,curMax);
        }
    };
    
    
    
    展开全文
  • 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的...我们有大量的节点与其祖先差值,其中一些如下: |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| =

    给定二叉树的根节点 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 之间。
    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        private: int result=0;
    public:
        int maxAncestorDiff(TreeNode* root) {
           dfs(root,-1,100001);
           return result;
        }
    private: 
           int dfs(TreeNode* root,int maxn,int minn)
           {
               if(!root) return 0; 
             if(root->val>maxn)    maxn=root->val;
               if(root->val<minn)    minn=root->val;
              int left= dfs(root->left,maxn,minn);
              int right= dfs(root->right,maxn,minn);
               result=max(result,maxn-minn);
               return max(left,right);
           }
    };
    
    展开全文
  • 1026. 节点与其祖先之间最大差值 题目描述 解题思路 回溯法 max_val, min_val记录子树到叶子节点最大、最小值 叶子节点计算最大差值 代码实现 # Definition for a binary tree node. # class TreeNode: # def __...


    1026. 节点与其祖先之间的最大差值

    题目描述

    在这里插入图片描述

    解题思路

    回溯法
    max_val, min_val记录子树到叶子节点最大、最小值
    叶子节点计算最大差值

    代码实现

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def maxAncestorDiff(self, root: TreeNode) -> int:
            # 回溯法
            # max_val, min_val记录子树到叶子节点最大、最小值
            # 叶子节点计算最大差值
            self.max_val = float("-inf")
            self.min_val = float("inf")
            self.seq = []
            self.res = float("-inf")
            def pre_order(root):
                if not root:
                    return
                self.seq.append(root.val)
    
                self.max_val = max(self.seq)
                self.min_val = min(self.seq)
                if not root.left and not root.right:
                    self.res = max(self.res, abs(self.max_val - self.min_val))
    
                pre_order(root.left)
                pre_order(root.right)
    
                self.seq.pop()
                    
            pre_order(root)
            return self.res
    
    
    展开全文
  • 节点与其祖先之间最大差值 题目 给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是...

    Leetcode 1026. 节点与其祖先之间的最大差值

    题目

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

    示例 1:

    在这里插入图片描述

    输入:root = [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:
    在这里插入图片描述

    输入:root = [1,null,2,null,0,3]
    输出:3
    

    思路

    • 首先, 遇到树的题目首选递归, 递归肯定也是分成根 —— 左 —— 右
    • 题目要求求出|A.val - B.val|最大值, 实际上就是求所有从根到叶子的最大的差值
    • 但是我们遍历到一个节点的时候,如何通过当前节点的val来更新res?难道我们还要记录路径?
    • 不需要, 求|A.val - B.val|最大值实际上只需要记录路径上节点的Max, Min, Max - Min就是所求值
    • 所以我们的递归参数记录Max, Min即可

    代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        void dfs(int& res, TreeNode* root, int Min, int Max) {
            if (!root) return;
        
            Min = min(Min, root->val);
            Max = max(Max, root->val);
            res = max(Max - Min, res);
            dfs(res, root->left, Min, Max);
            dfs(res, root->right, Min, Max);
        }
    
        int maxAncestorDiff(TreeNode* root) {
            int res = 0;
            dfs(res, root, INT_MAX, INT_MIN);
            return res;
        }
    };
    
    展开全文
  • 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的...
  • 题目描述: 给定二叉树的根节点 root,找出存在于 不同 节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。...我们有大量的节点与其祖先差值,其中一些如下: |8 - 3| = 5 |3 - 7| = 4 |8 -
  • 节点与其祖先之间最大差值 class Solution { public int maxAncestorDiff(TreeNode root) { int leftmax = maxAncestorDiff2(root.left,root.val,root.val); int rightmax = maxAncestorDif...
  • 给定二叉树的根节点root,找出存在于不同节点A 和B之间最大值 V,其中V = |A.val - B.val|,且A是B的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) ...
  • Maximum Difference Between Node and Ancestor(C++节点与其祖先之间最大差值
  • 题目: 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的...我们有大量的节点与其祖先差值,其中一些如下: |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 -
  • 节点与其祖先之间最大差值 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的...
  • 给定二叉树的根节点root,找出存在于不同节点A 和B之间最大值 V,其中V = |A.val - B.val|,且A是B的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,...我们有大量的节点与其祖先的差...
  • 节点与其祖先之间最大差值 * @author 作者 Your-Name: * @version 创建时间:2020年3月5日 上午9:44:01 * 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且...
  • 给定二叉树的根节点root,找出存在于不同节点A 和B之间最大值 V,其中V = |A.val - B.val|,且A是B的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) ...
  • 题目描述 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子...我们有大量的节点与其祖先的...
  • 节点与其祖先之间最大差值 1 题目描述(Leetcode题目链接)   给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一...
  • 遍历每条路径,寻找当前路径上的最大差值。dfs函数的参数为当前节点,路径上已遍历到的最大值与最小值。这种做法的关键在于祖先节点向子节点传递信息,在子节点处运算。当然用适当的数据结构记录左右子树分别的最大...
  • 思路:首先肯定是递归来实现,从根节点开始计算,和每个子节点之间最大差值,然后递归自身,将左子树和右子树作为递归开始,代码如下 class Solution { int max = 0; public int maxAncestorDiff(TreeNode root...
  • 给定二叉树的根节点root,找出存在于不同节点A和B之间最大值V,其中V = |A.val - B.val|,且A是B的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) ...
  • 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。 (如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的...
  • 一、Problem 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间最大值 V,其中 V = |A.val - B.val|,且 A 是 B...我们有大量的节点与其祖先差值,其中一些如下: |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 189
精华内容 75
关键字:

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