解法二思路和算法代码复杂度分析

[8,3,10,1,6,null,14,null,null,4,7,13]

\texttt{root

[8,3,10,1,6,null,14,null,null,4,7,13]}

root

[8,3,10,1,6,null,14,null,null,4,7,13]

\texttt{7}

二叉树中的每个结点对应一条从根结点到该结点的路径路径存在最大结点值和最小结点值。

对于每个结点该结点与其祖先之间的最大差值可能是以下两种情况之一

可以使用深度优先搜索计算二叉树中的每个结点与其祖先之间的最大差值。

从根结点开始遍历全部结点由于同一条路径上的结点的遍历顺序是从上到下在访问到一个结点时该结点的所有祖先结点都已经被访问过因此可以得到从根结点到该结点的路径上的最大结点值和最小结点值计算当前结点与其祖先之间的最大差值。

在访问一个结点之后对于其非空子结点更新从根结点到子结点的路径上的最大结点值和最小结点值对子结点继续遍历。

题目要求计算差值的两个结点应满足两个结点不同且一个结点是另一个结点的祖先。

上述做法虽然没有考虑计算差值的两个结点是否相同但是也能得到正确的结果理由如下。

2因此一定存在两个不同的结点且这两个结点之间存在祖先和后代的关系。

任何一个结点与其自身的差值一定是

0如果结点值不同则差值大于

0因此一定存在两个不同的结点这两个结点之间存在祖先和后代的关系且这两个结点值之差的绝对值等于最大差值。

class

是二叉树的结点数。

空间复杂度主要是栈空间取决于二叉树的高度最坏情况下二叉树的高度是

O(n)

也可以使用广度优先搜索计算二叉树中结点与祖先之间的最大差值。

从根结点开始遍历全部结点访问结点的顺序为层数递增的顺序遍历过程中对于每个结点得到该结点对应的从根结点到该结点的路径上的最大结点值和最小结点值计算该结点与其祖先之间的最大差值。

为了记录每个结点对应的从根结点到该结点的路径上的最大结点值和最小结点值需要使用三个队列分别存储结点、路径上的最大结点值和路径上的最小结点值这三个队列分别为结点队列、最大值队列和最小值队列初始时将根结点入结点队列将根结点值入最大值队列和最小值队列。

每次将一个结点、一个最大值和一个最小值分别从结点队列、最大值队列和最小值队列出队列计算当前结点与其祖先之间的最大差值。

对于当前结点的非空子结点计算从根结点到子结点的路径上的最大结点值和最小结点值然后将子结点以及子结点对应的最大结点值和最小结点值分别入结点队列、最大值队列和最小值队列。

class

ArrayDequeTreeNode();QueueInteger

maxNode

ArrayDequeInteger();QueueInteger

minNode

ArrayDequeInteger();nodeQueue.offer(root);maxNode.offer(root.val);minNode.offer(root.val);while

{TreeNode

{nodeQueue.offer(left);maxNode.offer(Math.max(left.val,

maxValue));minNode.offer(Math.min(left.val,

minValue));}if

{nodeQueue.offer(right);maxNode.offer(Math.max(right.val,

maxValue));minNode.offer(Math.min(right.val,

minValue));}}return

是二叉树的结点数。

空间复杂度主要是队列空间队列内元素个数不超过