首页 > 代码库 > 530. 平衡二叉树中，相邻节点的最小差 Minimum Absolute Difference in BST

530. 平衡二叉树中，相邻节点的最小差 Minimum Absolute Difference in BST

2024-09-23 08:03:21   213人阅读

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

   1
         3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.


  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left;
  6.  *     public TreeNode right;
  7.  *     public TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public int GetMinimumDifference(TreeNode root) {
  12. 		if (root == null) {
  13. 			return 0;
  14. 		}
  15. 		int min = Int32.MaxValue;
  16. 		Stack<TreeNode> stack = new Stack<TreeNode>();
  17. 		TreeNode current = root;
  19. 		while (current != null) {
  20. 			stack.Push(current);
  21. 			current = current.left;
  22. 		}
  23. 		while (stack.Count != 0) {
  24. 			current = stack.Pop();
  26. 			if (stack.Count > 0) {
  27. 				int diff = Math.Abs(stack.Peek().val - current.val);
  28. 				min = Math.Min(diff,min);
  29. 			}
  31. 			TreeNode node = current.right;
  32. 			while (node != null) {
  33. 				stack.Push(node);
  34. 				node = node.left;
  36. 				if (stack.Count > 0) {
  37. 					int diff = Math.Abs(stack.Peek().val - current.val);
  38. 					min = Math.Min(diff,min);
  39. 				}
  41. 			}
  42. 		}
  43. 		return min;
  44.     }
  45. }




null


530. 平衡二叉树中，相邻节点的最小差 Minimum Absolute Difference in BST


联系
我们