Trees

Validate Binary Search Tree

Assume BST特指： left subtree contains nodes less than node's key; right subtree contains nodes larger than node's key;

所以在这个问题上，如果要以recursion的思路解决的话，每一个节点告诉自己的父节点的信息为 True or False. 但是每一层的判断准侧与范围又是不一样的，所以每一层需要向上一层传递范围

class Solution {
  public boolean helper(TreeNode node, Integer lower, Integer upper) {
    if (node == null) return true;

    int val = node.val;
    if (lower != null && val <= lower) return false;
    if (upper != null && val >= upper) return false;

    if (! helper(node.right, val, upper)) return false;
    if (! helper(node.left, lower, val)) return false;
    return true;
  }

  public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
  }
}

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

用Recursive进行解决，首先要明确退出条件是：length == 0

class Solution{
public:
    TreeNode* sortedArrayToBST(vector<int>& num){
        return sortedArrayToBST(RandomAccessIterator first,
                                RandomAccessIterator end); 
    }
    
    template<typename RandomAccessIterator> TreeNode* 
      sortedArrayToBST(RandomAccessIterator first, 
                      RandomAccessIterator end){
          const auto length = distance(first, end);
          if(length <= 0) return nullptr;
          
          auto mid = first + length / 2;
          TreeNode* root = new TreeNode(*mid);
          root-> left = sortedArrayToBST(first, mid);
          root-> right = sortedArrayToBST(mid+1, end);
          return root;
      }
}

Convert Sorted to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

class Solution{
public:
    TreeNode* sortedListToBST(ListNode* head){
        return sortedListToBST(head, listLen(head));
    }
    
    TreeNode* sortedLisrToBST(ListNode* head, int len){
        if(len == 0) return nullptr;
        if(len == 1) return new TreeNode(head->val);
        TreeNode* root = new TreeNode(nth(head, len/2 + 1) -> val);
        root->left = sortedLisrToBST(head, len/2);
        root->right = sortedLisrToBST(nth(head, len/2 + 2), (len-1)/2);
        return root;
    }
    
    int listLen(ListNode* hed){
        int n = 0;
        while(hed){
            ++n;
            hed = hed->next;
        }
        return n;
    }
    
}

Minimum Depth of Binary Tree

顾名思义

def minDepth(root):
    if root == None:
        return 0
    if root.left == None and root.right == None:
        return 1
        
    if root.left == None
        return 1 + self.minDepth(root.right)
    
    if root.right == None:
        return 1 + self.minDepth(root.left)
        
     return min(self.minDepth(root.left) + self.minDepth(root.right)) + 1 

Path Sum

Path Sum II - LeetCodeLeetCode

class Solution(object):
    def pathSum(self, root, sum):
        res = []
        self.auxPath(root, res, sum, tmp)
        return res
    
    def auxPath(self, root, res, sum, tmp):
        if not root:
            return
        if sum == 0 and not root.left and root.right:
            res.append(tmp.append(root.val))
            return res
            
        if root.left:
            self.auxPath(root.left, res, sum - root.val, tmp + [root.val])
        if root.right:
            self.auxPath(root.right, res, sum - root.val, tmp + [root.val])