# 

## 

### 

********
********
********



- 
- 

#### 

```c++
void preorderTraversal(TreeNode *root)  {
    if (!root) {
        return;
    }
    cout val left);
    preOrderTraversal(root->right);
}
```

#### 

```c++
// V3
void preorderTraversal(TreeNode *root) {
    if (!root) {
        return;
    }
    auto stack = vector();
    while (root || !stack.empty()) {
        if (!root) {
            root = stack.back();
            stack.pop_back();
        }
        cout val right) {
            stack.push_back(root->right);
        }
        root = root->left;
    }
}
```

#### 

```c++
// stack 
void inorderTraversal(TreeNode *root) {
    if (!root) {
        return;
    }
    auto stack = vector();

    while (root || !stack.empty()) {
        while (root) {
            stack.push_back(root);
            root = root->left;
        }
        root = stack.back();
        stack.pop_back();
        cout val right;
    }
}
```

#### 

```c++
void postorderTraversal(TreeNode *root) {
    if (!root) {
        return;
    }
    auto stack = vector();
    TreeNode *lastPop = nullptr;
    while (root || !stack.empty()) {
        // 
        while (root) {
            stack.push_back(root);
            root = root->left;
        }
        root = stack.back();
        // 
        // 
        // 
        if (root->right && root->right != lastPop) {
            root = root->right;
            continue;
        }
        cout val val);
    dfs(root->left, result);
    dfs(root->right, result);
}
```

#### DFS -

```c++
// V2
vector preOrderTraversal(TreeNode *root) {
    return divideAndConquer(root);
}

vector divideAndConquer(TreeNode *root) {
    vector result;
    if (!root) {
        return result;
    }
    // (Divide)
    auto left = divideAndConquer(root->left);
    auto right = divideAndConquer(root->right);
    // (Conquer)
    result.push_back(root->val);
    result.insert(result.end(), left.begin(), left.end());
    result.insert(result.end(), right.begin(), right.end());
    return result;
}
```



> DFS  

#### BFS 

```c++
vector levelOrder(TreeNode *root) {
    vector result;
    if (!root) {
        return result;
    }
    queue queue;
    queue.push(root);
    while (!queue.empty()) {
        root = queue.front();
        result.push_back(root->val);
        if (root->left) {
            queue.push(root->left);
        }
        if (root->right) {
            queue.push(root->right);
        }
        queue.pop();
    }

    return result;
}
```

### 





- 
- 
- 



- 
- 
- 

```c++
ResultType traversal(TreeNode *root) {
    // nil or leaf
    if (!root) {
        // do something and return
    }

    // Divide
    auto left = traversal(root->left);
    auto right = traversal(root->right);

    // Conquer
    auto result = merge(left, right);

    return result;
}
```

#### 

```c++
// V2
vector preOrderTraversal(TreeNode *root) {
    return divideAndConquer(root);
}

vector divideAndConquer(TreeNode *root) {
    vector result;
    if (!root) {
        return result;
    }
    // (Divide)
    auto left = divideAndConquer(root->left);
    auto right = divideAndConquer(root->right);
    // (Conquer)
    result.push_back(root->val);
    result.insert(result.end(), left.begin(), left.end());
    result.insert(result.end(), right.begin(), right.end());
    return result;
}
```

####  

```c++
template
static void MergeSort(T arr[], int len) {
    auto tmp = new T[len];
    mergeSort(arr, 0, len - 1, tmp);
    delete[] tmp;
}

template
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
    if (begin + 1 >= end) {
        return;
    }

    auto mid = begin + (end - begin) / 2;
    auto begin1 = begin;
    auto end1 = mid;
    auto begin2 = mid + 1;
    auto end2 = end;
    mergeSort(arr, begin1, end1, tmp);
    mergeSort(arr, begin2, end2, tmp);

    // merge two parts
    auto index = begin;
    while (begin1  



```c++
int maxDepth(TreeNode* root) {
    if (!root) {
        return 0;
    }
    // divide
    auto leftDepth = maxDepth(root->left);
    auto rightDepth = maxDepth(root->right);
    
    // conquer
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
```

#### balanced-binary-tree

[balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)

> 

 &&  &&  0 

```c++
bool isBalanced(TreeNode *root) {
    return maxDepth(root) != -1;
}

int maxDepth(TreeNode *root) {
    if (!root) {
        return 0;
    }
    auto left = maxDepth(root->left);
    auto right = maxDepth(root->right);
    if (left == -1 || right == -1 || left - right > 1 || right - left > 1) {
        return -1;
    }
    return (left > right ? left : right) + 1;
}
```



> 

#### binary-tree-maximum-path-sum

[binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

> ****



```c++
int maxPathSum(TreeNode *root) {
    auto maxSum = std::numeric_limits::min();
    calcMaxPath(root, maxSum);
    return maxSum;
}

int calcMaxPath(TreeNode *&root, int &maxSum) {
    if (!root) {
        return 0;
    }
    // 0
    auto left = max(calcMaxPath(root->left), 0);
    auto right = max(calcMaxPath(root->right), 0);

    // ""+
    // 
    // 
    // right + left + root->val = 0 + 0 + root->val
    maxSum = max(maxSum, left + right + root->val);
    // +
    //  + 
    return max(left, right) + root->val;
}
```

#### lowest-common-ancestor-of-a-binary-tree

[lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

> , 



```c++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) {
        return nullptr;
    }
    //  root
    if (root == p || root == q) {
        return root;
    }
    // Divide
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    // Conquer
    // 
    if (left && right) {
        return root;
    }
    return left ? left : right;
}
```

### BFS 

#### binary-tree-level-order-traversal

[binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

>  ****  

 O(logN)

```c++
vector levelOrder(TreeNode* root) {
    vector ret;
    if (!root) {
        return ret;
    }
    queue queue;
    queue.push(root);
    while (!queue.empty()) {
        vector levelValues;
        for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {
            auto node = queue.front();
            queue.pop();
            levelValues.push_back(node->val);
            if (node->left) {
                queue.push(node->left);
            }
            if (node->right) {
                queue.push(node->right);
            }
        }
        ret.push_back(levelValues);
    }
    return ret;
}
```

#### binary-tree-level-order-traversal-ii

[binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)

>  



```c++
vector levelOrderBottom(TreeNode *root) {
    auto result = levelOrder(root);
    reverse(result);
    return result;
}

vector levelOrder(TreeNode *root) {
    vector ret;
    if (!root) {
        return ret;
    }
    queue queue;
    queue.push(root);
    while (!queue.empty()) {
        vector levelValues;
        for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {
            auto node = queue.front();
            queue.pop();
            levelValues.push_back(node->val);
            if (node->left) {
                queue.push(node->left);
            }
            if (node->right) {
                queue.push(node->right);
            }
        }
        ret.push_back(levelValues);
    }
    return ret;
}

void reverse(vector &result) {
    for (int i = 0, j = result.size() - 1; i < j; ++i, --j) {
        swap(result[i], result[j]);
    }
}
```

#### binary-tree-zigzag-level-order-traversal

[binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)

> Z 

```c++
vector zigzagLevelOrder(TreeNode* root) {
    vector ret;
    if (!root) {
        return ret;
    }
    queue queue;
    queue.push(root);
    auto l2r = true;
    while (!queue.empty()) {
        vector levelValues;
        for (auto levelNodeNum = queue.size(); levelNodeNum > 0; --levelNodeNum) {
            auto node = queue.front();
            queue.pop();
            levelValues.push_back(node->val);
            if (node->left) {
                queue.push(node->left);
            }
            if (node->right) {
                queue.push(node->right);
            }
        }
        if (l2r) {
            ret.emplace_back(levelValues);
        } else {
            ret.emplace_back(
                    levelValues.rbegin(),
                    levelValues.rend()
            );
        }
        l2r = !l2r;
    }
    return ret;
}
```

### 

#### validate-binary-search-tree

[validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)

> 

 1

 2 MAX <  <  MIN

```c++
// v1
bool isValidBST(TreeNode *root) {
    if (!root) {
        return true;
    }
    //  1
    auto inOrderValues = vector();
    inOrder(root, inOrderValues);
    for (auto iter = inOrderValues.cbegin() + 1; iter != inOrderValues.cend(); ++iter) {
        if (*(iter - 1) >= *iter) {
            return false;
        }
    }
    return true;
}

void inOrder(TreeNode *root, vector &values) {
    if (!root) {
        return;
    }
    inOrder(root->left, values);
    values.push_back(root->val);
    inOrder(root->right, values);
}
```

```c++
// v2
struct Result {
    TreeNode *maxNode;
    TreeNode *minNode;
    bool isValidate;

    Result(bool validate = true, TreeNode *max = nullptr, TreeNode *min = nullptr)
            : isValidate(validate), maxNode(max), minNode(min) {

    }
};
bool isValidBST(TreeNode *root) {
    if (!root) {
        return true;
    }
    return helper(root).isValidate;
}

Result helper(TreeNode *root) {
    if (!root) {
        return {};
    }
    auto left = helper(root->left);
    auto right = helper(root->right);
    if (!(left.isValidate && right.isValidate)) {
        return {false};
    }
    if (left.maxNode && left.maxNode->val >= root->val) {
        return {false};
    }
    if (right.minNode && right.minNode->val val) {
        return {false};
    }
    return {
            true,
            right.maxNode ? right.maxNode : root,
            left.minNode ? left.minNode : root,
    };
}
```

#### insert-into-a-binary-search-tree

[insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)

> BST 



```c++
// DFS
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return root;
    }

    if (root->val > val) {
        root->left = insertIntoBST(root->left, val);
    } else {
        root->right = insertIntoBST(root->right, val);
    }
    return root;
}
```

## 

- 
-  DFS 
-  BFS 

## 

- [ ] [maximum-depth-of-binary-tree](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
- [ ] [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
- [ ] [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
- [ ] [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
- [ ] [binary-tree-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
- [ ] [binary-tree-level-order-traversal-ii](https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
- [ ] [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
- [ ] [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
- [ ] [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)