@Configuration
public class WebMvcConfig extends WebMvcConfigurationSupport {
    @Override
    protected void addResourceHandlers(ResourceHandlerRegistry registry) {
        registry.addResourceHandler("/front/**").addResourceLocations("classpath:/static/front/");
        registry.addResourceHandler("/backend/**").addResourceLocations("classpath:/static/backend/");
    }
}

@Mapper
public interface EmployeeMapper extends BaseMapper<Employee> {
}

public interface EmployeeService extends IService<Employee> {
}

@Service
public class EmployServiceImpl extends ServiceImpl<EmployeeMapper, Employee> implements EmployeeService {
}

@Data
public class Result<T> {
    private Integer code; //编码：1成功，0和其它数字为失败
    private String msg; //错误信息
    private T data; //数据
    private Map map = new HashMap(); //动态数据

    public static <T> Result<T> success(T object) {
        Result<T> result = new Result<T>();
        result.data = object;
        result.code = 1;
        return result;
    }

    public static <T> Result<T> error(String msg) {
        Result result = new Result();
        result.msg = msg;
        result.code = 0;
        return result;
    }

    public Result<T> add(String key, Object value) {
        this.map.put(key, value);
        return this;
    }
}

@Slf4j
// caution here, RestController 注解的value是用于为组件起一个逻辑名称
@RestController
@RequestMapping("/employee")
public class EmployeeController {

    @Autowired
    private EmployeeService employeeService;

    /**
     * create by: Xin Liu
     * description: 这个控制器负责后台系统的登陆和登出功能
     * create time: 2023/4/13 2:42 PM
     *
      * @param employee 封装前端页面请求传入的JSON数据
     * @return fun.xinliu.entity.Employee
     */
    @PostMapping("/login")
    public Result<Employee> login(HttpServletRequest httpServletRequest,  @RequestBody Employee employee) {

        String username = employee.getUsername();
        String password = employee.getPassword();
        password = DigestUtils.md5DigestAsHex(password.getBytes());

        LambdaQueryWrapper<Employee> lqw = new LambdaQueryWrapper<>();
        lqw.eq(Employee::getUsername,username);
        Employee emp = employeeService.getOne(lqw);

        if(emp == null) {
            return Result.error("该用户名或密码不正确");
        }

        if(!emp.getPassword().equals(password)){
            return Result.error("该用户名或密码不正确");
        }

        if(emp.getStatus() == 0){
            return Result.error("该账户已被禁用，请联系管理员");
        }
      
        // 为什么要记录登陆id？
        // 为了后续校验当前访问请求是否已经登陆
        httpServletRequest.getSession().setAttribute("employee", emp.getId());

        return Result.success(emp);
    }
}

@PostMapping("/logout")
public Result<String> logout(HttpServletRequest request) {
    // 清理session中保存的当前登陆的员工id
    request.getSession().removeAttribute("employee");
    return Result.success("退出成功");
}

@WebFilter(filterName = "loginCheckFilter", urlPatterns = "/*")
@Slf4j
public class LoginCheck implements Filter {

    public static final AntPathMatcher PATH_MATCHER = new AntPathMatcher();

    @Override
    public void doFilter(ServletRequest servletRequest, ServletResponse servletResponse, FilterChain filterChain) throws IOException, ServletException {
        HttpServletRequest request = (HttpServletRequest) servletRequest;
        HttpServletResponse response = (HttpServletResponse) servletResponse;

        // 获取本次请求的URI
        String requestURI = request.getRequestURI();

        // 列出无需拦截的urls
        String[] urls = new String[] {
                "/employee/login", "/employee/logout", "/backend/**", "/front/**"
        };

        // 判断本次请求是否需要处理，如果符合exclude的pattern则直接放行
        if(check(urls, requestURI)) {
            filterChain.doFilter(request,response);
            return;
        }

        // 否则判断是否已经登陆, 如果已经登陆则放行
        if(request.getSession().getAttribute("employee") != null) {
            filterChain.doFilter(request,response);
            return;
        }

        // 如果未登陆，则写数据返回前端
        // 注意这里写的数据需要和前端进行协作，要符合指定的数据交换规范
        response.getWriter().write(JSON.toJSONString(Result.error("NOTLOGIN")));
    }
		
  	// helper函数，负责进行校验
    public boolean check(String[] urls, String requestURI) {
        for (String s:urls) {
            boolean match = PATH_MATCHER.match(s, requestURI);
            if(match){
                return true;
            }
        }
        return false;
    }
}

@PostMapping
public Result<String> save(HttpServletRequest httpServletRequest, @RequestBody Employee employee) {
    log.info("新增员工： {}", employee.toString());

    // 设置一个初始密码，需要使用md5进行加密
    employee.setPassword(DigestUtils.md5DigestAsHex("123456".getBytes()));
    
    employee.setCreateTime(LocalDateTime.now());
    employee.setUpdateTime(LocalDateTime.now());

    Long empId = (Long)httpServletRequest.getSession().getAttribute("employee");

    employee.setUpdateUser(empId);
    employee.setCreateUser(empId);

    employeeService.save(employee);
    return Result.success("新增员工成功");
}

@ControllerAdvice(annotations = {RestController.class, Controller.class})
@ResponseBody
@Slf4j
public class GlobalExceptionHandler {

    @ExceptionHandler(SQLIntegrityConstraintViolationException.class)
    public Result<String> exceptionHandler(SQLIntegrityConstraintViolationException ex) {
        log.error(ex.getMessage());

        if(ex.getMessage().contains("Duplicate entry")){
            String[] strings = ex.getMessage().split(" ");
            String msg = "用户名" + strings[2] + "已存在";
            return Result.error(msg);
        }
      
        return Result.error("未知错误");
    }
}

v@Data
public class Employee implements Serializable {

    //省略了其他字段
    @TableField(fill = FieldFill.INSERT)
    private LocalDateTime createTime;

    @TableField(fill = FieldFill.INSERT_UPDATE)
    private LocalDateTime updateTime;

    @TableField(fill = FieldFill.INSERT)
    private Long createUser;

    @TableField(fill = FieldFill.INSERT_UPDATE)
    private Long updateUser;
}

@Component
@Slf4j
public class MyMetaObjectHandler implements MetaObjectHandler {
    @Override
    public void insertFill(MetaObject metaObject) {
        log.info("公共字段填充（create）...");
        metaObject.setValue("createTime", LocalDateTime.now());
        metaObject.setValue("updateTime", LocalDateTime.now());
        //设置创建人id
        metaObject.setValue("createUser", BaseContext.getCurrentId());
        metaObject.setValue("updateUser", BaseContext.getCurrentId());
    }

    @Override
    public void updateFill(MetaObject metaObject) {
        log.info("公共字段填充（insert）...");
        metaObject.setValue("updateTime", LocalDateTime.now());
        //设置更新人id
        metaObject.setValue("updateUser", BaseContext.getCurrentId());
    }
}

/**
 * create by: Xin Liu
 * description: 基于ThreadLocal的封装工具类，用于保存和获取当前登陆用户的id
 * create time: 2023/4/14 4:00 PM
 */
public class BaseContext {

    private static ThreadLocal<Long> threadLocal = new ThreadLocal<>();

    public static void setCurrentId(Long id) {
        threadLocal.set(id);
    }

    public static Long getCurrentId() {
        return threadLocal.get();
    }
}

class Solution {
    public int maxProfit(int[] prices) {

        int profit = 0;
        int diff = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            diff = prices[i + 1] - prices[i];

            // purchase iff next day's price is higher than today's
            if (diff > 0){
                profit += diff;
            }
        }

        return profit;
    }
}

class Solution {
    public boolean canJump(int[] nums) {

        if (nums.length == 1) {
            return true;
        }

        int approach = nums[0];

        for (int i = 0; i <= approach; i++) {
            approach = Math.max(approach, i + nums[i]);
            if(approach >= nums.length - 1) {
                return true;
            }
        }

        return false;
    }
}

class Solution {
    public int jump(int[] nums) {

        if (nums.length == 1) {
            return 0;
        }

        int curRange = 0;
        int potential = 0;
        int res = 0;

        // here our traverse stops at i == nums.length -2
        // if as this case, i == curRange, it naturally
        // need one more step, and res would increase by 1
        // else, it means that the curRangg has already covered
        // the nums.length - 1
        for (int i = 0; i < nums.length - 1; i++) {
            
            potential = Math.max(potential, i + nums[i]);

            if (i == curRange) {
                res++;
                curRange = potential;
            }
        }

        return res;
    }
}

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int index = s.length - 1;
        int num = 0;

        for (int i = g.length - 1; i >= 0; i--) {

            if (index < 0) {
                break;
            }

            if (s[index] >= g[i]) {
                num++;
                index--;
            }
        }
        return num;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
        
        // corner case, as described, if there are only 1 element return 1
        // if there are two elements and they are not equal, return 2
        if (nums.length == 1) {
            return 1;
        }else if (nums.length == 2) {
            if (nums[0] != nums[1]) {
                return 2;
            }
            return 1;
        }

        // result is initialized as 1, as the rightest one is always regarded as a waggle
        int result = 1;

        // 
        int prevDiff = 0;
        int curDiff = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            if (prevDiff >= 0 && curDiff < 0 || prevDiff <=0 && curDiff > 0) {
                result++;
                // update prevDiff only when a waggle is found, and recordsits direction
                prevDiff = curDiff;
            }
        }

        return result;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {

        int sum = Integer.MIN_VALUE;
        int temp = 0;

        for (int i = 0; i < nums.length; i++) {
            temp += nums[i];

            // do the comparasion first, and initialize sum to minimum to avoid no result recorded
            sum = temp > sum ? temp : sum;

            // temp is a temporaray record of local sum, if it is less than zero, then it makes no sense
            // to further sum
            if (temp < 0) {
                temp = 0;
            }
        }

        return sum;

    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private Set<List<Integer>> set = new HashSet<>();
    private List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {

        backtracking(nums, 0);
        ans.addAll(set);
        return ans;

    }

    private void backtracking (int[] nums, int startIndex) {

        // as the minimum valid sequence contains at least two elements, thus 
        // add those path whose length is greater than 1
        if (path.size() > 1) {
            set.add(new LinkedList<>(path));
        }
        

        for (int i = startIndex; i < nums.length; i++) {

            /*
             * actually this kind of remove duplicate is non-sense
             * as it only function when the given array is like [4 6 7 7]
             * if it is changed to [4 7 6 7] it still causes duplicates
             */

            // rule out duplicate elements in same level
            if (i > startIndex && nums[i] == nums[i - 1]){
                continue;
            }

            // we are not sure whether this time of calling would
            // add a element or not ,thus record the previous size
            int recordPathSize = path.size();

            // for the topest level elements, directly add it
            if (path.size() == 0) {
                path.add(nums[i]);
            }else if (path.size() > 0) {
                // if current element is greater and equals to last added element
                if ( nums[i] >= path.get(path.size() - 1)){
                    path.add(nums[i]);
                }
            }

            // recursively call this func
            backtracking(nums, i + 1);

            // if we do add elements into the path, remove it 
            if (path.size() > recordPathSize) {
                path.remove(path.size() - 1);
            }
        }
    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {

        backtracking(nums, 0);
        return ans;

    }

    private void backtracking (int[] nums, int startIndex) {
        
        // when traversing all the tree, add those path whose length is equal
        // and greater than 2 
        if (path.size() > 1) {
            ans.add(new LinkedList<>(path));
        }

        // number [-100, 100] maps to array ranged [0, 200]
        // records whether this num has been used 
        int[] used = new int[201];

        for (int i = startIndex; i < nums.length; i++) {

            // if path is not empty and elment is less than last num or it has been used, skip
            if ( (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || used[nums[i] + 100] == 1 ) {
                continue;
            }

            path.add(nums[i]);
            used[nums[i] + 100] = 1;

            backtracking(nums, i + 1);

            // avoid uncertain backtrack, ensure that whichever approach here must be successful add
            path.remove(path.size() - 1);           
        }
    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtracking(nums);
        return ans;
    }

    private void backtracking (int[] nums) {
        
        // exits
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
        }
        
        for (int i = 0; i < nums.length; i++) {

            if(used[i]) {
                continue;
            };

            path.add(nums[i]);
            used[i] = true;

            backtracking(nums);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();
    private boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtracking(nums);
        return ans;
    }

    private void backtracking (int[] nums) {
        
        // exits
        if (path.size() == nums.length) {
            ans.add(new LinkedList<>(path));
        }
        
        for (int i = 0; i < nums.length; i++) {

            // here is pruning but in a branch level
            // as used[i - 1] = true means we are in the branch of nums[i -1]
            // which is less efficient than directly remove this whole branch 

            // if(used[i] || (i > 0 && used[i - 1] && nums[i] == nums[i - 1])) {
            //     continue;
            // };
            
            // here is the pruning in level level (the same level on the tree)
            if(used[i] || (i > 0 && !used[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            };

            path.add(nums[i]);
            used[i] = true;

            backtracking(nums);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {

    List<String> ans = new LinkedList<>();
    List<String> path = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) {
            return ans;
        }
        backtracking(s, 0, 0);
        return ans;
    }

    private void backtracking (String s, int startIndex, int cnt) {

        // recursion exits
        if (cnt == 4) {
            if (startIndex >= s.length()) {
                String str = path.stream().collect(Collectors.joining("."));
                ans.add(str);
            }
            return;
        }
        
        for (int i = startIndex; i < s.length() - (4 - path.size()) + 1; i++) {
            // if the subString from [startIndex, i] is valid
            String subStr = s.substring(startIndex, i + 1);
            if (isValidIP(subStr)){
                
                path.add(subStr);
            }else {
                continue;
            }
            backtracking(s, i + 1, cnt + 1);
            path.remove(path.size() - 1);
        }
    }


    // used to check the given string is valid ip or not
    private boolean isValidIP (String str) {

        if (str != null) {

            if (str.length() > 3) {
                return false;
            }

            int num = Integer.valueOf(str) ;

            if (num < 0 || num > 255) {
                return false;
            }

            if (str.length() > 1 && str.charAt(0) == '0') {
                return false;
            }
            return true;
        }
        return false;
    }
}

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();

    // high complexity
    // public List<List<Integer>> subsets(int[] nums) {

    //     for (int i = 0; i <= nums.length; i++) {
    //         backtracking1(nums, i, 0);
    //     }
        
    //     return res;
    // }

    // private void backtracking1 (int[] nums, int k, int index) {
    //     // recursion exits
    //     if (path.size() == k) {
    //         List<Integer> sub = new LinkedList<>();
    //         sub.addAll(path);
    //         res.add(sub);
    //         return;
    //     }

    //     // this is to remove those unvalid recursion
    //     for (int i = index; i < nums.length - (k - path.size()) + 1; i++) {
    //         path.add(nums[i]);
    //         backtracking(nums, k, i + 1);
    //         path.remove(path.get(path.size() - 1));
    //     }
    // }


    public List<List<Integer>> subsets(int[] nums) {
        helper(nums, 0);
        return res;
    }

    private void helper ( int[] nums, int startIndex) {

        // add very node during traverse
        res.add(new LinkedList<>(path));

        if (startIndex >= nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            
            path.add(nums[i]);
            helper(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {

    List<List<Integer>> ans = new LinkedList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // as there are duplicates elements, thus we need to sort the array first
        Arrays.sort(nums);
        backtracking(nums, 0);
        return ans;
    }

    private void backtracking (int[] nums, int startIndex) {
        ans.add(new LinkedList<>(path));

        for (int i = startIndex; i < nums.length; i++) {

            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }else {
                path.add(nums[i]);
            }

            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(target, candidates, 0);
        return ans;
    }

    private void backtracking (int target, int[] candidates, int startIndex) {

        // if target is less than 0, exits
        if (target < 0) {
            return;
            // if find a successful combo, add it into ans
        }else if (target == 0) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            ans.add(combo);
        }


        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);

            // note here, by seting the startIndex to i , it means that
            // the next element can still start with candidates[i]
            // this allows path like [2,2,3]
            // but at the mean time, it prevents the path like [3,2,2]
            // and through this way it removes some duplicates path
            backtracking(target - candidates[i], candidates, i);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();
    private List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);

        backtracking(candidates, target, 0);

        return ans;
    }

    private void backtracking(int[] candidates, int target, int index) {

        if (target < 0) {
            return;
            // if find a successful combo, add it into ans
        }else if (target == 0) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            ans.add(combo);
        }

        for (int i = index; i < candidates.length; i++) {
						
            // we need to avoid the duplicates in the same level for instance, 
          	// if we are chooseing the first num and the candidates is [1, 1, 1, 2]
          	// then the second 1 would result in duplicates
            // this num is same as its left one && they are in the same level
            // then skip it
            if (i > index && candidates[i] == candidates[i - 1]){
                continue;
            }

            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {

    private List<List<String>> ans = new LinkedList<>();
    private List<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return ans;

    }

    // for any String such as "aabbccd"
    // start with "a" then "aa", then "aab" 
    private void backtracking (String s, int startIndex) {

        // if we succeed to split the whole string, return
        if (startIndex >= s.length()) {
              List<String> combo = new LinkedList<>();
              combo.addAll(path);
              ans.add(combo);
              return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            
            if (isPalindrome(s, startIndex, i)) {
                path.add(s.substring(startIndex, i + 1));
            }else {
                continue;
            }

            backtracking(s, i + 1);
            path.remove(path.size() - 1);
            
        }

    }

    // test if a sub string is palindrome from startIndex to the endIndex
    private boolean isPalindrome (String s, int startIndex, int endIndex) {
        int i = startIndex;
        int j = endIndex;

        boolean ans = true;

        while ( i <= j) {
            if (s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else {
                ans = false;
                break;
            }
        }

        return ans;
    }
}

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new LinkedList<>();
        List<Integer> path = new LinkedList<>();
        backtracking(res, path, k, n, 1);
        return res;
    }

    private void backtracking (List<List<Integer>> res, List<Integer> path, int k, int n, int index) {

        // recursion exits if size == k && sum == n
        if (path.size() == k && getSum(path) == n) {
            List<Integer> combo = new LinkedList<>();
            combo.addAll(path);
            res.add(combo);
        }

        // traverse the [index, 9]
        for (int i = index; i < 10; i++) {
            // add this value into path
            path.add(i);

            // traverse the right side numbers
            backtracking(res, path, k, n, i + 1);

            // backtrack here
            path.remove(path.get(path.size() - 1));
        }

    }

    // a helper method
    private int getSum ( List<Integer> list) {
        int sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }
        return sum;
    }
}

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> ans = new LinkedList<>();
        List<Character> path = new LinkedList<>();

        if (digits.length() > 0) {
            backtracking(map, ans, path, digits);
        }

        return ans;

    }

    private void backtracking (Map<Character, String> map, List<String> ans, List<Character> path, String digits) {

        // recursion exits if the length approach its target
        if (path.size() == digits.length()) {

            StringBuffer sb = new StringBuffer();

            for (Character character : path) {
                sb.append(character);
            }

            ans.add(new String(sb));
            return;
        }

        char digit = digits.charAt(path.size());
        String str = map.get(digit);

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            path.add(c);

            backtracking(map, ans, path, digits);

            // false way
            // path.remove(path.get(path.size() - 1));

            // correct one
            path.remove(path.size() - 1);
        }

    }
}

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> path = new LinkedList<>();
        myCombine(ans, path, n, k, 1);
        return ans;
    }

    // for instance, n = 20, K = 3,
    // the tartet ans is the combination of every 2 elements in [1, 20]
    private void myCombine (List<List<Integer>> ans, List<Integer> path, int n, int k, int index) { 
        
        // recursion exits
        if (path.size() == k) {
            List<Integer> combine = new LinkedList<>();
            combine.addAll(path);
            ans.add(combine);
            return;
        }
        
        // this is to remove those unvalid recursion
        for (int i = index; i <= n - (k - path.size()) + 1 ; i++) {
            path.add(i);
            myCombine(ans, path, n, k, i + 1);
            path.remove(path.get(path.size() - 1));

        }
 
    }

}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        
        if (root == null) {
            return null;
        }
				
				// as this is a BST, if root's val is larger than high 
				// then all the right side nodes should be removed
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
				
				// the same with the left side
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
				
				// else, it means that root is within the target range
				// thus trim its child nodes
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;

    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // as I do not wanna change the array itself thus I choose to use to helper
        // function and express the range 
        return buildBST(nums, 0, nums.length);
    }


    // build the tree and return the root node in range [startIndex, endIndex)
    private TreeNode buildBST (int[] nums, int startIndex, int endIndex){
        
        if (startIndex >= endIndex) {
            return null;
        }

        // pre-order
        int mid = (endIndex - startIndex) / 2 + startIndex;
        TreeNode root = new TreeNode (nums[mid]);
        
      	// maitain the invirants- the range [startIndex, endIndex)
        root.left = buildBST(nums, startIndex, mid);
        root.right = buildBST(nums, mid + 1, endIndex);
        return root;

    }
}

class Solution {
    private int temp = Integer.MIN_VALUE;

    public TreeNode convertBST(TreeNode root) {

        myConvertTree(root);
        return root;
    }


    private void myConvertTree (TreeNode root) {
        
        if (root == null) {
            return;
        }

        // reflect the target tree, we can find that it starts counting 
        // with the right node, then root node
        // and then the left node, thus we can traverse the tree in a variant in-order
        // i.e. right mid left 
        myConvertTree(root.right);

        // use a temp variable to record the updated value of the prev node thus we can 
        // change all the nodes in one traverse
        if (temp != Integer.MIN_VALUE) {
            root.val += temp;
        }

        temp = root.val;

        myConvertTree(root.left);
    }

}