Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
Example :
Input: root = [4,2,6,1,3,null,null] Output: 1 Explanation: Note that root is a TreeNode object, not an array. The given tree [4,2,6,1,3,null,null] is represented by the following diagram: 4 / 2 6 / 1 3 while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.
Note:
- The size of the BST will be between 2 and 100.
- The BST is always valid, each node's value is an integer, and each node's value is different.
分析¶
这道题目其实考察的是二叉树的中序遍历,二叉树的中序遍历是一个递增序列,好像是错的。。。。。但是通过了AC。
待续。。。。
public int minDiffInBST(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; int prev = 0, min = Integer.MAX_VALUE, count = 0; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); if (count != 0) { int diff = cur.val - prev; if (diff < min) min = diff; } count++; prev = cur.val; cur = cur.right; } return min; }





近期评论