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

本文主要是介绍dfs，LeetCode 1026. 节点与其祖先之间的最大差值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

2、接口描述

python3

​

# 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: Optional[TreeNode]) -> int:

cpp

​

/*** 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:int maxAncestorDiff(TreeNode* root) {}
};

3、原题链接

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

---

二、解题报告

1、思路分析

我们从根往下dfs，维护路径上的最大值ma最小值mi，当遇到空节点时，我们用ma - mi维护最大差值

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)，递归栈开销

3、代码详解

python3

​

# 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: Optional[TreeNode]) -> int:ret = 0def dfs(rt: Optional[TreeNode], mi: int, ma: int) -> None:if not rt:nonlocal retret = max(ret, ma - mi)returnma = max(ma, rt.val)mi = min(mi, rt.val)dfs(rt.left, mi, ma)dfs(rt.right, mi, ma)dfs(root, root.val, root.val)return ret

cpp

​

/*** 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:int maxAncestorDiff(TreeNode* root) {int ret = 0;function<void(TreeNode*, int, int)> dfs = [&](TreeNode* rt, int mi, int ma){if(!rt) {ret = max(ret, ma - mi);return;}dfs(rt->left, min(mi, rt->val), max(rt->val, ma));dfs(rt->right, min(mi, rt->val), max(rt->val, ma));};dfs(root, root->val, root->val);return ret;}
};

这篇关于dfs，LeetCode 1026. 节点与其祖先之间的最大差值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---