【leetcode刷题】T140-二叉搜索树的最小绝对差

示例:
输入:
   1
    \
     3
    /
   2

输出:
1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 中序遍历，得到所有元素
        ls = []
        self.get_elements(root, ls)
        val = sys.maxsize
        for i in range(1, len(ls)):
            val = min(val, abs(ls[i] - ls[i-1]))
        return val

    def get_elements(self, node, ls):
        if not node:
            return 
        self.get_elements(node.left, ls)
        ls.append(node.val)
        self.get_elements(node.right, ls)

/**
 * 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 getMinimumDifference(TreeNode* root) {
        // 中序遍历，得到所有节点值
        vector<int> ls;
        order_traval(root, ls);
        int val = INT_MAX;
        for(int i=1; i < ls.size(); i++){
            val = min(val, abs(ls[i] - ls[i-1]));
        }
        return val;
    }

    void order_traval(TreeNode* node, vector<int>& ls){
        if(!node)
            return ;
        order_traval(node->left, ls);
        ls.push_back(node->val);
        order_traval(node->right, ls);

    }
};