> For the complete documentation index, see [llms.txt](https://nuoxu2016.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nuoxu2016.gitbook.io/algorithms/trees.md).

# 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. 但是每一层的判断准侧与范围又是不一样的，所以每一层需要向上一层传递范围

```java
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

```cpp
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.

```cpp
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

顾名思义

```python
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

{% embed url="<https://leetcode.com/problems/path-sum-ii/>" %}

```python
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])
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nuoxu2016.gitbook.io/algorithms/trees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.