# Welcome!

Oliver's Blog

## Hello there!    |    你好, 旅行者

This is where I write stuff down, possibly including study notes, random thoughts, solutions to some issues, etc. Here are some links to my others pages:

### Portfolio Website

{% embed url="<https://yushunchen.com/>" %}

### Course Guide

{% embed url="<https://yushunchen.com/courses-new.html>" %}

### GitHub Page

{% embed url="<https://github.com/yushunchen>" %}

## This page is constantly under construction... (hopefully) 🚧🚧🚧


# RISC Game

## Introduction

RISC game stands for Really Interesting Strategic Conquest game. This is a multiplayer web-based strategic game, accommodating up to 4 players, where they can conquer territories, strategize movement and upgrades for soldiers, and utilize random game cards.

## Game Deployment

Game deployment is easy because Docker is employed to streamline the process. I reserved a publicly accessible VM at our school with an IP address of <http://vcm-33920.vm.duke.edu/>. The game repository can be accessed here:

{% embed url="<https://github.com/YushunChen/risc-game>" %}

On the VM,

```bash
git clone https://github.com/YushunChen/risc-game.git
sudo apt install docker-compose
cd risc-game
sudo docker-compose build
sudo docker-compose up
```

Then, the game is up and running and can be access at <http://vcm-33920.vm.duke.edu:3000/>

## Game Features

### Sign in/Register

<figure><img src="/files/6kPxdNqZ50IajBvHbMaN" alt=""><figcaption><p>Register</p></figcaption></figure>

<figure><img src="/files/Sc0YzxJYKTaIO7apS6Ng" alt=""><figcaption><p>Sign in</p></figcaption></figure>

The user has to register first if they have not done so. They can log back into the game and continue plays a previous game they have participated in.

### Game List

<figure><img src="/files/LJVkt605F9k6QCtapbeE" alt=""><figcaption><p>Game List</p></figcaption></figure>

Once the user is logged in, they are able to create games based on the number of players available. They can join a new game by finding available games that have already been created. They can start or continue to play a game by simply clicking the green "Play" button on the left card.

### Game Play

<figure><img src="/files/VatQRapkHaym6fHgDwnq" alt=""><figcaption><p>Game Play</p></figcaption></figure>

The detailed game play is rather complicated since the game had 3 iterations in terms of requirements definitions. Here are the detailed requirements:

{% file src="/files/n3vipVSmkNFiDLbLyEJ1" %}
Iteration 1
{% endfile %}

{% file src="/files/pceql2vMO2B5cz2p1Yky" %}
Iteration 2
{% endfile %}

{% file src="/files/F2olzrtbxm9J3ZeTivRE" %}
Iteration 3
{% endfile %}

Now, I will highligh some of the major features of the game.

#### Game Goal

The goal of this game is to conquer territories on the map.&#x20;

#### Move and Attack

Each territory has some number of soldiers defending it. Players can move their soldiers to their own territories for attacking or defending purposes.&#x20;

<figure><img src="/files/6DXpnIYcyiYLplbXzzSR" alt=""><figcaption><p>Different Types of Soldiers in a Territory</p></figcaption></figure>

The more soldier you have in a territory, the more likely you are able to win a battle if you attack another territory or another player attacked your territory. Also, each territory has different food and technology resources so its value vary. The players can gain food and technology resources that are generated from their territories.

#### Research

<figure><img src="/files/7mvz0IiWjYF3jUHVEbeE" alt=""><figcaption><p>Player Info</p></figcaption></figure>

<figure><img src="/files/X3Dsk2kTZvkGGNHJRC7o" alt=""><figcaption><p>Research Order</p></figcaption></figure>

Each player has a technology level as seen on far right of the player info card. This allows them to upgrade their soldier to be more powerful, which means more likely to win battles.

#### Upgrade

<figure><img src="/files/ijamfCuj7Q5nQoL0XFjW" alt=""><figcaption><p>Upgrade Order</p></figcaption></figure>

Upgrade order basically upgrades some number of soldiers which is allowed by the technology level.

#### Card

The players can draw 3 random cards each turn that have either positive or negative effects on their gameplay. There is a probability distribution designed to avoid abusing the card drawing system because the cards that are effective (other than no luck card) are powerful in the game. Each player can draw 3 cards per turn, and the cards are played automatically.

* CARD\_CONQUERING\_WARRIORS: (10% chance of drawing): This card would add one Level-6 unit to every territory owned by the player, even if the player does not have a sufficient tech level for level-6 units.
* CARD\_FAMINE: (10% chance of drawing): This card is a negative effect card which would stop the tech/food resource creation for the player for the next round.
* CARD\_UNBREAKABLE\_DEFENCE: (10% chance of drawing): This card would give the player an opportunity to defend one of their territories no matter the opponent.  Defending players would not lose any units from that territory; however, opponents would lose all their attacking units.&#x20;
* CARD\_NO\_LUCK: (70% chance of drawing): This card would not have any effect on the gameplay and the player would waste drawing a card.

<br>

<figure><img src="/files/FcPbVn6zjAIzAXBS7lFn" alt=""><figcaption><p>Draw Cards</p></figcaption></figure>

<figure><img src="/files/hUomJbOzOjbEhBRhJrXp" alt=""><figcaption><p>Example Card</p></figcaption></figure>

#### Spy

Spy is a special type of soldier that you can deploy to enemy territories. By doing so, you are able to see territories that you are not supposed to. By the game rules, you are only able to see territories that are directly adjacent to your own territories. Other territories are invisible as seen on the map.&#x20;

#### Cloak

Once the player reached technology level 3, he can cloak a territory, which means hiding the territory from the enemies. This cloaking hides from adjacent viewing, but not from spies.

<figure><img src="/files/eHu8o7sGuiW1ypA4NL4H" alt=""><figcaption><p>Cloak Order</p></figcaption></figure>

Here are only the main features in a nutshell. Make sure to check out the actual game yourself! :)

## Project Management

### Project Repo

{% embed url="<https://github.com/YushunChen/risc-game>" %}
Project Repo
{% endembed %}

This is only a duplicate version of the GitLab repo that we actually used. Unfortunately, the GitLab repo is only internally visible.

### Task Breakdown

{% embed url="<https://docs.google.com/spreadsheets/d/16xOkD3LADTxXVlDQQskP6GXHTisLs_BV8FibdgjboJo/edit#gid=1206966973>" %}

### UML Diagram

{% embed url="<https://drive.google.com/file/d/1JpOCZlAWN01cRub0nu00rUbWBVIAo0vw/view>" %}


# Mini Amazon

## Introduction

This is a scalable full-stack web application simulating Amazon where the users can browse products, buy them, and track the order. The application is implemented using Django and PostgreSQL. Here is the detailed requirements for this project:

{% file src="/files/mXESgMnAodLw2MoPjBgH" %}

Here is the project repository:

{% embed url="<https://github.com/YushunChen/mini-amazon>" %}

## App Deployment

<figure><img src="/files/B5GQghA0RWdZU5tACdPP" alt=""><figcaption><p>Project Setup</p></figcaption></figure>

Three essential parts are needed for the complete functionality of this app.

1. Mini Amazon (this application itself)
2. Mini UPS (implemented by other teams)
3. World (a warehouse system under the `world_simulator_exec` directory)

## App Features

### Login/Sign up

<figure><img src="/files/OXGUcFjT6rhOvgxUPS8M" alt=""><figcaption><p>Login</p></figcaption></figure>

<figure><img src="/files/pwP2HMrrMQCL7Cu4KyJK" alt=""><figcaption><p>Sign up</p></figcaption></figure>

The user is able to login to the Mini Amazon store or sign up for a new account. Django authentication is used to ensure security and robustness of the web application.

### Search and Filter

<figure><img src="/files/c4ZRUNfCHDIiRAhJ2goj" alt=""><figcaption><p>Search / Home Page 1</p></figcaption></figure>

<figure><img src="/files/ft4uyJg5Q8JW0T6UWql0" alt=""><figcaption><p>Home Page 2</p></figcaption></figure>

<figure><img src="/files/w1nKBr3SG1FBptmcmpUc" alt=""><figcaption><p>Home Page 3</p></figcaption></figure>

<figure><img src="/files/4dTk5bk6LY6cjevf40i6" alt=""><figcaption><p>Home Page 4</p></figcaption></figure>

<figure><img src="/files/BqGBgrGuJgDxbWuFGQuN" alt=""><figcaption><p>Filter</p></figcaption></figure>

Users have the convenience of searching for various product categories available in the web store, such as gloves, enhancing their browsing experience. Additionally, a user-friendly categories dropdown feature allows for effortless filtering of desired items, ensuring a seamless shopping experience.

### Place Orders

<figure><img src="/files/GZa19UruDdd7ZyMULVEa" alt=""><figcaption><p>Place Orders</p></figcaption></figure>

The user can buy products by placing an order where they specify their address (a Cartesian coordinate), product, product count, and their email. Once the order is placed, a confirmation email will be sent to the user.

### Check Order Status

The user can check the status of any of their orders. The time that takes to process the orders depends on the speed of the world simulator, whose details can be read in this repo:

{% embed url="<https://github.com/yunjingliu96/world_simulator_exec>" %}

The status are updated according to the interactions among the three components of the app: Mini Amazon, Mini UPS, and the world simulator.

### Contact

<figure><img src="/files/KbIUsJT1Z6xlWV4vSWMU" alt=""><figcaption><p>Contact</p></figcaption></figure>

To facilitate effective communication between users and the Mini Amazon store, a user-friendly email functionality is incorporated, allowing users to easily send emails for inquiries or concerns. This feature ensures seamless interactions and fosters better customer support, enhancing overall user satisfaction.


# HTTP Caching Proxy

Introducing My HTTP Caching Proxy Project: A High-Performance, Scalable Solution As part of my efforts to deepen my understanding of networking, HTTP protocols, and high-performance server development

## Introduction

As part of my efforts to deepen my understanding of networking, HTTP protocols, and high-performance server development, I created an **HTTP Caching Proxy** server as a course project. This proxy server is designed to handle HTTP requests and responses efficiently while caching the results to improve response times. The proxy is fully built in **C++**, leveraging advanced techniques like **multi-threading**, **I/O multiplexing** with **epoll**, and caching mechanisms based on **LRU (Least Recently Used)**.

## What is an HTTP Caching Proxy?

In simple terms, an HTTP proxy server acts as an intermediary between a client (such as a web browser) and an origin server (like a website). It forwards requests from the client to the server and sends back the server's response. By caching frequently requested content, a proxy server can significantly reduce the time it takes to fetch resources from the origin server and minimize bandwidth usage.

In my project, the caching proxy not only forwards requests and responses but also intelligently caches **GET** requests with a **200-OK** status code and checks for cache validity based on **expiration times** and **re-validation** strategies. This reduces the number of requests that need to be sent to the origin server and ensures faster browsing for users.

## Key Features and Architecture

### **1. High-Performance Design**

I implemented the proxy server with **multi-threading** to handle multiple concurrent connections efficiently. By employing the **epoll** API for **I/O multiplexing**, the server can handle thousands of requests simultaneously without blocking. The server is designed using the **master-slave Reactor** pattern to separate the management of incoming connections from the actual request handling. This design ensures that the server scales well and remains responsive under high load.

### **2. Efficient Caching with LRU**

A core feature of the proxy is its caching mechanism. The server uses an **LRU (Least Recently Used)** cache, meaning that the most frequently accessed resources are kept in memory, while less frequently used ones are evicted. This mechanism is crucial in ensuring that the cache stays within memory limits while maximizing performance. Additionally, cached responses are validated based on **Cache-Control** headers and **ETags**, which is consistent with the HTTP specification.

### **3. Log Management**

A robust **logging system** is implemented to track every interaction with the proxy server. Each request is assigned a unique **ID**, and detailed logs are generated for requests, cache status, origin server interactions, and responses. This ensures that both users and developers can monitor and debug the server's behavior. The logs are stored in **/var/log/erss/proxy.log** inside the container and are accessible on the host machine via a mounted volume for easy analysis.

### **4. Error Handling**

The proxy is designed to handle various errors gracefully, including:

* **Malformed requests** (400 Bad Request)
* **Server errors** (502 Bad Gateway)
* **Expired or corrupted cached data**

If the origin server responds with an error or corrupted data, the proxy responds with the appropriate HTTP error code. This fault tolerance ensures a reliable experience even in the face of unexpected issues.

### **5. HTTPS and Tunneling Support**

The proxy also supports **HTTPS** requests, which require the **CONNECT** method. For secure connections, the proxy opens a tunnel to the origin server and forwards encrypted data back and forth. The server logs when a tunnel is opened and closed, providing transparency into these interactions.

### **6. Dockerized for Easy Deployment**

To facilitate easy deployment and testing, I containerized the proxy using **Docker**. A `docker-compose.yml` file and `Dockerfile` were created to allow the proxy to run as a Docker container. The container is configured to map port **12345** on the host machine to the proxy, and logs are saved in a directory on the host system, ensuring that developers can easily track the proxy's performance and behavior.

#### Technical Details and Implementation

* **Programming Language**: C++
* **Networking**: Linux Sockets, TCP
* **Concurrency**: Multi-threading, Epoll, Thread Pool, Reactor Pattern
* **Caching**: LRU Algorithm, Cache Expiration, Cache Re-validation
* **HTTP Protocols Supported**: GET, POST, CONNECT (with optional support for other methods)
* **Error Handling**: Graceful handling of server errors and malformed requests
* **Deployment**: Docker, Docker Compose

### Performance Improvements and Benchmarks

One of the key highlights of this project was improving the **response time** of the proxy. By using an LRU caching mechanism and ensuring that expired or stale cache entries were properly handled, the proxy was able to **reduce response time by 30%** compared to a non-caching setup.

The proxy was designed to handle over **10,000 concurrent connections**, and thanks to the **epoll-based I/O multiplexing** and **thread pool**, it could scale to meet high demand. This makes it well-suited for production environments where performance is critical.

#### Logs and Debugging

The logging system I implemented provides detailed insights into the behavior of the proxy server. Every request and response is logged with a **unique ID** and includes information about:

* The incoming request (method, URL, headers)
* The cache status (whether the response was served from cache, if it was expired, etc.)
* The server interactions (requests made to the origin server, responses received)
* Responses sent back to the client

This logging mechanism is invaluable for debugging issues and understanding the server's internal state at any given time.

#### Conclusion

This HTTP Caching Proxy project allowed me to gain hands-on experience in **network programming**, **server design**, and **high-performance systems**. By implementing an efficient multi-threaded proxy with caching, I was able to deliver significant performance improvements for web browsing, while ensuring robust error handling and system monitoring.


# Course Enrollment App

## Introduction

This is a web application built with React.js. It is a project from the course CS571: Building User Interfaces at UW-Madison.

## Project Details

### Interaction Design: Structure, Layout, & Navigation

{% file src="/files/jF4pJFe4biWUrCpLMNMR" %}

### Heuristic Evaluation

{% file src="/files/38zjvdOGqxwiCmGf3hY1" %}


# Fitness Tracker App

## Introduction

This is a mobile application built with React Native. It is a project from the course CS571: Building User Interfaces at UW-Madison. This project focused on building mobile applications using prototyping and accessible designs.

## Project Details

### Prototyping

{% file src="/files/OHpEhYzGK3yjyfOV86VM" %}

### Accessible Design

{% file src="/files/Lsc9SkG90sDRWID39inp" %}

### Video Demo

{% embed url="<https://youtu.be/ffxxzRuNOPo>" %}

{% embed url="<https://youtu.be/BkbOvtotHTo>" %}


# Voice Shopping Assistant

## Introduction

This is a web application built with JavaScript and [Dialogflow](https://cloud.google.com/dialogflow/docs). It is a project from the course CS571: Building User Interfaces at UW-Madison. This project focused on building a web application that can be navigated with voice commands from the users.

## Project Details

### Conversational Interactions

{% file src="/files/X8aGg1aGAVDVaxtIrncy" %}

### Usability Testing

{% file src="/files/gjZRww3gLLzCxGr4quvL" %}

### Video Demo

{% embed url="<https://youtu.be/rTK4CWkmUH0>" %}


# Graphics Town

## Introduction

This is a web application built with [Three.js](https://threejs.org/). It is a project from the course CS559: Computer Graphics at UW-Madison. This is an individual project with no detailed requirements. Everyone demonstrates their own artistic and programmatical skills and abilities in this project.

## Project Details

### 3D Object List

1. Pool-1\*: A big pool with textured water using customized shaders and textured walls.
2. Bridge-1\*: A bridge with customized drawing using shaders that alternates its colors.
3. BlueHouse-1\*: A textured blue house using geometries written from scratch.&#x20;
4. Church-1\*: A textured church using geometries written from scratch.&#x20;
5. Castle-1\*: A textured castle using geometries written from scratch.&#x20;
6. Truck-1\*: A textured Amazon Prime truck that stops at buildings in the residential area.&#x20;
7. Car-1\*: A textured Mercedes Benz car that runs around the town.
8. Carousel-1\*: A colorful carousel ride with rotating horses.
9. Earth-1\*: A textured earth with normal/bump mapping that rotates
10. Globe-1\*: A globe that reflects its surroundings above the pool in the town.
11. Helicopter-1\*: A helicopter that circles around in the sky of the town.
12. Road-1\*: The road structure of the entire town.
13. RoundaboutBall-1\*: A rotating roundabout that has a ball that moves up and down and changes its color according to the color of its collision plane.
14. Seesaw-1\*: A seesaw that goes back and forth with moving objects on each side.
15. Tower-1\*: A tower ride with rotating poles that are attached to swinging horizontal pads.
16. Tree-Cartoon-1\*: A caroon tree with animated leaves, used in the amusement park area.
17. Tree-Realistic-1\*: A realistic tree with textured leaves, used in the residential area.
18. ParkGate-1\*: The textured front gate of the amusement park.&#x20;
19. Fence-1\*: The fence structures that are used around the amusement park.

### Some Basic Behaviors

1. Car-1\*: The red car goes around the town.
2. Helicopter-1\*: The helicopter rotating propellers flies over the town.
3. Tower-1\*: The tower ride has rotating poles that are attached with swinging horizontal pads.
4. Truck-1\*: The Amazon Prime truck goes around the town and stops at some buildings for a random amount of time in the residential area.
5. Carousel-1\*: The colorful carousel ride has rotating horses that bounce up and down.&#x20;
6. Seesaw-1\*: The seesaw has a horizontal bar that goes back and forth with moving objects on each side.&#x20;
7. Bridge-1\*: The bridge has alternating colors.&#x20;
8. Tree-Cartoon-1\*: The cartoon trees have animated leaves.&#x20;
9. RoundaboutBall-1\*: The rotating roundabout has a ball that moves up and down and changes its color according to the color of its collision plane.

### Some Advanced Behaviors

1. Bridge-1\* (Animated Shader Effect): The bridge is built using customized drawing with shaders and it alternates its colors.
2. Truck-1\* (Complex Behavior): The Amazon Prime truck goes around the town and turns properly at the intersections (big circle concrete). The truck stops at some buildings for a random amount of time in the residential area.
3. Pool-1\* (Curved Surface): The big pool has curved surface using customized shaders and textured walls.
4. Globe-1\* (Dynamic Environment Map): The globe reflects its surroundings above the pool in the town.

### Texture Attributions

1. BlueHouse-1\*:
   1. Body texture (building2.jpg): <https://www.pinterest.com/pin/535646949415150665/>
   2. Roof texture (blue\_tiles.jpg): <https://www.dreamstime.com/texture-blue-house-roof-texture-blue-house-roof-image174230093>
2. Church-1\*:
   1. Body texture (building1.jpg): <https://www.energy.gov/energysaver/doors>
   2. Roof texture (roof\_tiles.jpg): <https://www.textures.com/browse/wood/2133>
3. Castle-1\*:
   1. Castle body texture (castle.png): <https://www.dreamstime.com/photos-images/castle-door.html>
   2. Castle roof texture (castle\_top.jpg): <https://libreshot.com/old-roof-window/>
   3. Pillar body texture (pillar.jpg): <https://www.wildtextures.com/category/free-textures/stone/>
   4. Pillar top texture (pillar\_top.png): <https://motionarray.com/stock-photos/irregular-stone-texture-910664/>
4. Truck-1\*:
   1. Amazon license plate texture (amazon.jpg): <https://www.freepnglogos.com/pics/amazon-png-logo-vector>
   2. Window texture (car\_window\.jpg): <https://www.dreamstime.com/fog-car-window-glass-texture-background-image132822015>
   3. Amazon Prime logo texture (prime.png): <https://www.flickr.com/photos/160866001@N07/50597570511>
5. Car-1\*:
   1. Benz logo texture (benz.png): <https://logosarchive.com/mercedes-benz/>
   2. Window texture (car\_window\.jpg): <https://www.dreamstime.com/fog-car-window-glass-texture-background-image132822015>
   3. Body texture (redcar.jpg): <https://tr.pinterest.com/pin/628674429222816370/>
6. Earth-1\*:
   1. Earth texture (earth.jpg): <https://www.flickr.com/photos/42084302@N05/3884071286/in/photostream/>
7. Pool-1\*:
   1. Water texture (water.jpg): <https://www.flickr.com/photos/41246865@N04/4877078316/>
   2. Round wall texture (brick.jpg): <https://www.flickr.com/photos/coun2rparts/3508864763/in/photolist-6m4Rfk-9sMJeh-5A6jji-attjHR-7LCYQL-atvZcS-atthvg-atvUEd-atw2eG-FeEGuT-atvVUj-dmNZAU-FkPcRw-zxo9Le-nHKPBW-9sJK1D-atvXeq-attoVp-7TgSPm-7TdDpc-97nYto-ciQ2Eo-ymgiym-ciQ3n3-yDCqEx-EqHfNR-ymgjJh-ymhmEN-EVvFm5-yCT3xX-xFRwgf-Fo5gBe-ymhoPN-ohzAhj-zmuiDn-Ar4NW4-oEtLqk-8FmWCn-9newMS-dyxotb-7TdFyr-93bnjY-9bikgt-918vHa-jrYqc-z4TUEU-TCqz8o-ejvH3m-ymgeys-TCqxzJ>
8. Tree-Realistic-1\*:
   1. Trunk texture (trunk.jpg): <https://www.textures.com/category/tree-bark/544>
   2. Leaves texture (leaves.png): <https://www.istockphoto.com/illustrations/leaf-texture>
9. ParkGate-1\*:
   1. 3D object and its textures: <https://free3d.com/3d-model/driveway-gate-old-80884.html>
10. Fence-1\*:
    1. 3D object: <https://sketchfab.com/3d-models/basic-fence-c5229ed4813c4d1396406805e8756166>

### Picture Demo

![](/files/pgTzasisqvShGLK8ewTy) ![](/files/Y8dH6lJh9ssNOr6PYo9o) ![](/files/36gjT2NwezGJsjQZ7eBY) ![](/files/bo5RgfWeXWZxriRzhIHU)

### Video Demo

{% embed url="<https://youtu.be/gBCOsl8ggQI>" %}


# Binary Search


# Classical Binary Search

ID: 457; easy; 经典二分查找问题

{% embed url="<https://www.lintcode.com/problem/457/>." %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        return -1;
    }
}
```

### Notes

* The loop condition `left + 1 < right` will guarantee that we end up with two indices that are next to each other. Then, we return either of them at the end.
* The middle point `mid` is calculated using `left + (right - left) / 2` instead of `(left + right) / 2` in order to prevent integer overflow, which the addition may have while the subtraction will not.


# First Position of Target

ID: 14; easy; 二分查找

{% embed url="<https://www.lintcode.com/problem/14/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        return -1;
    }
}
```

### Notes

* This is very similar to the classical binary search. However, we do not return mid when we immediately find a value because we are not sure if it is the first position. So, we only reduce the range. Eventually we have the range `[left, right]` that contains the target and we return `left` if possible to ensure that it is the first position of target.


# Last Position of Target

ID: 458; easy; 目标最后位置

{% embed url="<https://www.lintcode.com/problem/458/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    public int lastPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0)  {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (nums[right] == target) return right;
        if (nums[left] == target) return left;
        return -1;
    }
}
```

### Notes

* This is almost the same as finding the [first position of target](/algo/binary-search/first-position-of-target). We return right if possible at the end to ensure that it is the last position of target.


# Guess Number Higher or Lower

ID: 662; easy; 猜数游戏

{% embed url="<https://www.lintcode.com/problem/662/>" %}

## Solution 1 (Java)

```java
/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    /**
     * @param n an integer
     * @return the number you guess
     */
    public int guessNumber(int n) {
        final int CORRECT = 0, GUESS_SMALLER = -1, GUESS_LARGER = 1;
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (guess(mid) == CORRECT) {
                return mid;
            } else if (guess(mid) == GUESS_SMALLER) {
                right = mid;
            } else { // (guess(mid) == GUESS_LARGER)
                left = mid;
            }
        }

        if (guess(left) == CORRECT) return left;
        if (guess(right) == CORRECT) return right;
        return 0;
    }
}
```

### Notes

* This is almost the same as [classical binary search](/algo/binary-search/classical-binary-search).


# Search in a Big Sorted Array

ID: 447; medium; 在大数组中查找

{% embed url="<https://www.lintcode.com/problem/447/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        int left = 0, right = 1;
        while (reader.get(right) < target) {
            right *= 2;
        }

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int midNum = reader.get(mid);
            if (midNum < target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (reader.get(left) == target) return left;
        if (reader.get(right) == target) return right;
        return -1;
    }
}
```

### Notes

* We do not know the upper bound of the range, so we double `right` starting from 1 until the element at right is larger than the `target`. Thus, we have a valid range containing a `target`.
* We cannot return `mid` immediately if we found a `target` because the problem requires the first position of the `target`.


# Total Occurrence of Target

ID: 462; easy; 目标出现总和

{% embed url="<https://www.lintcode.com/problem/462/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param A: A an integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    public int totalOccurrence(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }

        int start, end;
        int left = 0, right = A.length - 1;

        // find left end point of the range
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (A[left] == target) {
            start = left;
        } else if (A[right] == target) {
            start = right;
        } else {
            return 0;
        }

        // find right end point of the range
        left = 0; right = A.length -1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[right] == target) {
            end = right;
        } else if (A[left] == target) {
            end = left;
        } else {
            return 0;
        }

        return end - start + 1;
    }
}
```

### Notes

* We use the similar approach in the [first position of target](/algo/binary-search/first-position-of-target) and the [last position of target](/algo/binary-search/last-position-of-target) to find the left and right end points of the range for the `target`.
* Eventually, we return the length of that range.


# First Bad Version

ID; 74; medium; 第一个错误的代码版本

{% embed url="<https://www.lintcode.com/problem/74/>" %}

## Solution 1 (Java)

```java
/**
 * public class SVNRepo {
 *     public static boolean isBadVersion(int k);
 * }
 * you can use SVNRepo.isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
*/
public class Solution {
    /**
     * @param n: An integer
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        int left = 1, right = n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            boolean isBad = SVNRepo.isBadVersion(mid);
            if (isBad) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (SVNRepo.isBadVersion(left)) return left;
        if (SVNRepo.isBadVersion(right)) return right;
        return 0;
    }
}
```


# Find Minimum in Rotated Sorted Array

ID: 159; medium; 寻找旋转排序数组中的最小值

{% embed url="<https://www.lintcode.com/problem/159/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        int target = nums[nums.length - 1];

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return Math.min(nums[left], nums[right]);
    }
}
```

### Notes

* We use the last element as the target since we lack a target for the binary search. The reason is that we can reduce the range that contains the minimum number using this target.&#x20;
* Also, note that the array may not be rotated at all.&#x20;


# Maximum Number in Mountain Sequence

ID: 585; medium; 山脉序列中的最大值

{% embed url="<https://www.lintcode.com/problem/585/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: a mountain sequence which increase firstly and then decrease
     * @return: then mountain top
     */
    public int mountainSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]) {
                return nums[mid];
            } else if (nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return Math.max(nums[left], nums[right]);
    }
}
```


# Search a 2D Matrix

ID: 28; easy; 搜索二维矩阵

{% embed url="<https://www.lintcode.com/problem/28/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int row = matrix.length, col = matrix[0].length;
        int start = 0, end = row * col - 1;
        
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int midNum = matrix[mid / col][mid % col];
            if (midNum == target) {
                return true;
            } else if (midNum < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (matrix[start / col][start % col] == target) return true;
        if (matrix[end / col][end % col] == target) return true;
        return false;
    }
}
```


# Search a 2D Matrix II

ID: 38; medium; 搜索二维矩阵（二）

{% embed url="<https://www.lintcode.com/problem/38/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        int row = 0, col = matrix[0].length - 1;
        int targetCount = 0;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                targetCount++;
                row++;
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                col--;
            }
        }
        return targetCount;
    }
}
```

### Notes

* We pick a special number in the 2D matrix here. Either the **top right** element or the **bottom left** element will work. The reason is that we want to reduce the range in which we research for the `target`. In the code above, we chose the top right element and it is the largest in its row but the smallest in its column. Thus, if the `target` is larger than it, we proceed downward to find it; if the `target` is smaller than it, we proceed to the left. And if the `target` is equal to it, we increment the `targetCounter` and move diagonally since each number is unique in its row and column.


# Search for a Range

ID: 61; medium; 搜索区间

{% embed url="<https://www.lintcode.com/problem/61/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        if (A == null || A.length == 0) {
            return new int[]{-1, -1};
        }

        int[] range = new int[2];
        int left = 0, right = A.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (A[left] == target) {
            range[0] = left;
        } else if (A[right] == target) {
            range[0] = right;
        } else {
            range[0] = range[1] = -1;
            return range;
        }

        left = 0; right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[right] == target) {
            range[1] = right;
        } else if (A[left] == target) {
            range[1] = left;
        } else {
            range[0] = range[1] = -1;
            return range;
        }

        return range;
    }
}
```

{% hint style="info" %}
Similar to Total Occurrence of Target (ID: 462).
{% endhint %}


# Smallest Rectangle Enclosing Black Pixels

ID: 600; hard; 包裹黑色像素点的最小矩形

{% embed url="<https://www.lintcode.com/problem/600/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param image: a binary matrix with '0' and '1'
     * @param x: the location of one of the black pixels
     * @param y: the location of one of the black pixels
     * @return: an integer
     */
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return -1;
        }

        int row = image.length - 1, col = image[0].length - 1;
        int left = findLeftBound(image, 0, y);
        int right = findRightBound(image, y, col);
        int top = findTopBound(image, 0, x);
        int bottom = findBottomBound(image, x, row);

        return (right - left + 1) * (bottom - top + 1);
    }

    private int findLeftBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (colHasBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (colHasBlackPixel(image, start)) {
            return start;
        }
        return end;
    }

    private int findRightBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (colHasBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (colHasBlackPixel(image, end)) {
            return end;
        }
        return start;
    }

    private int findTopBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (rowHasBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (rowHasBlackPixel(image, start)) {
            return start;
        }
        return end;
    }

    private int findBottomBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (rowHasBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (rowHasBlackPixel(image, end)) {
            return end;
        }
        return start;
    }

    private boolean rowHasBlackPixel(char[][] image, int row) {
        for (int i = 0; i < image[0].length; i++) {
            if (image[row][i] == '1') return true;
        }
        return false;
    }
    
    private boolean colHasBlackPixel(char[][] image, int col) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][col] == '1') return true;
        }
        return false;
    }
}
```

### Notes

* We use binary search to find the left, right, top, and bottom boundaries of the black area. Specifically, we are trying to find 1's in these four directions and reduce the range if we cannot.&#x20;


# Find Peak Element

ID: 75; medium; 寻找峰值

{% embed url="<https://www.lintcode.com/problem/75/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    public int findPeak(int[] A) {
        int left = 0, right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > A[mid-1] && A[mid] > A[mid+1]) {
                return mid;
            } else if (A[mid] > A[mid-1] && A[mid] < A[mid+1]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return A[left] > A[right] ? left : right;
    }
}
```


# Search in Rotated Sorted Array

ID: 62; medium; 搜索旋转排序数组

{% embed url="<https://www.lintcode.com/problem/62/>" %}

{% embed url="<https://leetcode.com/problems/search-in-rotated-sorted-array/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) return -1;
        int left = 0, right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;

            // mid element on the left half
            if (A[mid] > A[left]) {
                if (target >= A[left] && target < A[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                // mid element on the right half
                if (target > A[mid] && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        if (A[left] == target) return left;
        if (A[right] == target) return right;
        return -1;
    }
}
```

### Notes

In order to perform a classical binary search, we need to have a strictly increasing or decreasing series. Here, the rotate array can be seen as two increasing arrays. We need to determine which half we should perform the operations on. Thus, we compare the `mid` element with the first element in the array to see which half the `mid` element is on currently.

#### I. The `mid` element is on the left half

The reason is that if the `mid` element is larger than the first element, by the construction of the rotated array, we know that the `mid` element is on the left half now. After this first check, we try to see where `target` is. We compare if the `target` is on the same half (left half) as the mid element. This comparison is simple checking if `target` is in between `A[left]` and `A[mid]`.

1. If `target` and the `mid` element are on the same half (`target` is on the left half), we can discard the right half of the array.
2. If they are on different halves (`target` is on the right half), we can discard the left half.

#### II. The `mid` element is on the right half

If the `mid` element is smaller than the first element, then it is on the right half. Similarly, we try to see where `target` is. If `target` is in between `A[mid]` and `A[right]`, then `target` is on the same half as the `mid` element (right half).&#x20;

1. If `target` and the `mid` element are on the same half (`target` is on the right half), we can discard the left half of the array.
2. If they are on different halves (`target` is on the left half), we can discard the right half.

### Example

{% tabs %}
{% tab title="Example 1" %}
`[4, 5, 6, 7, 0, 1, 2]` and `target = 5`

| left | right | mid | New Range      |
| ---- | ----- | --- | -------------- |
| 4    | 2     | 7   | `[4, 5, 6, 7]` |
| 4    | 7     | 5   | `[4, 5]`       |

Case I. 1.: The `mid` element and `target` are both on the left side. Loop terminates, the index of 5 is returned.
{% endtab %}

{% tab title="Example 2" %}
`[4, 5, 6, 7, 0, 1, 2]` and `target = 2`

| left | right | mid | New Range      |
| ---- | ----- | --- | -------------- |
| 4    | 2     | 7   | `[7, 0, 1, 2]` |
| 7    | 2     | 0   | `[0, 1, 2]`    |
| 0    | 2     | 1   | `[1, 2]`       |

Case I. 2. and Case II. 1.: To start with, the `mid` element and `target` are on different sides (`mid` is on the left, `target` is on the right). Then, after iteration 1, the `mid` element and `target` are on the same side.&#x20;

Loop terminates, the index of 2 is returned.
{% endtab %}

{% tab title="Example 3" %}
`[6, 7, 0, 1, 2, 3, 4, 5]` and `target = 6`

| left | right | mid | New Range      |
| ---- | ----- | --- | -------------- |
| 6    | 5     | 1   | `[6, 7, 0, 1]` |
| 6    | 1     | 7   | `[6, 7]`       |

Case II. 2. and Case I. 1.: To start with, the `mid` element and `target` are on different sides (`mid` is on the right, `target` is on the left). Then, after iteration 1, the `mid` element and `target` are on the same side.&#x20;

Loop terminates, the index of 6 is returned.
{% endtab %}

{% tab title="Example 4" %}
`[0, 1, 2, 3, 4, 5]` and `target = 4`

| left | right | mid | New Range              |
| ---- | ----- | --- | ---------------------- |
| 0    | 5     | 2   | `[2, 3, 4, 5]`         |
| 2    | 5     | 3   | `[3, 4, 5]`            |
| 3    | 5     | 4   | 4 immediately returned |

The algorithm works for non-rotated arrays as well. This can also be seen in previous examples.

Loop terminates, the index of 4 is returned.
{% endtab %}
{% endtabs %}


# Wood Cut

ID; 183; hard; 木材加工

{% embed url="<https://www.lintcode.com/problem/183/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0) 
            return 0;
        int maxLength = findMaxWoodLength(L);
        int left = 1, right = maxLength;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int counts = countPieces(L, mid);
            if (counts >= k) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (countPieces(L, right) >= k) return right;
        if (countPieces(L, left) >= k) return left;
        return 0;
    }

    private int findMaxWoodLength(int[] L) {
        int max = 0;
        for (int l : L) {
            max = Math.max(max, l);
        }
        return max;
    }

    private int countPieces(int[] L, int cutLength) {
        int counts = 0;
        for (int l : L) {
            counts += l / cutLength;
        }
        return counts;
    }
}
```

### Notes

There are two key requirements in this problem:

1. The woods need to be cut into `k` pieces of the same length.
2. The length of the pieces should be maximized.

We use binary search to search for the cut length, i.e., the length of the pieces. The initial range for this length is `[1, max]` where `max` is the maximum length among the woods. We take the middle number and count the number of pieces using that number as the cut length.&#x20;

* If `count ≥ k`, the first requirement is satisfied but we still need to test the second requirement, so we do not immediately return. Now the new range is `[mid, max]`.
* If `count < k`, the first requirement is not satisfied, which means we are cutting too much. Then, the new range is `[1, mid]`.

Lastly, we end up with the range `[left, right]`. To satisfy the two requirements, we would return `right` if possible since `right` is larger than `left`.


# Find the Duplicate Number

ID: 633; medium; 寻找重复的数

{% embed url="<https://www.lintcode.com/problem/633/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: an array containing n + 1 integers which is between 1 and n
     * @return: the duplicate one
     */
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (countSmallerNums(mid, nums) <= mid) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (countSmallerNums(left, nums) <= left)
            return right;
        return left;
    }

    private int countSmallerNums(int num, int[] nums) {
        int count = 0;
        for (int n : nums) {
            if (n <= num) count++;
        }
        return count;
    }
}
```

### Notes

* The array is not sorted
* Time complexity should be less than

$$
O(n^2)
$$

* Space complexity should be

$$
O(1)
$$

We know that the range of the numbers is initially `[1, n]`. We take the middle element inside the range `mid`. If `count ≤ mid`, where `count` is the number of elements that are less than or equal to `mid`, then we are certain that the duplicated number is not inside the range `[left, mid]`. The reason is the following:

{% tabs %}
{% tab title="Example 1" %}
Original array: `[3, 1, 4, 6, 5, 8, 8, 9]`&#x20;

Range: `[1, 9]`

| left | right | mid | count                                   | Result        |
| ---- | ----- | --- | --------------------------------------- | ------------- |
| 1    | 9     | 5   | 4 bc the smaller number are  3, 1, 4, 5 | `count ≤ mid` |

New range is `[5, 9]` and 8 is inside that range.:white\_check\_mark:&#x20;
{% endtab %}

{% tab title="Example 2" %}
Original array: `[3, 1, 1, 1, 4, 6, 5, 8]`&#x20;

Range: `[1, 8]`

| left | right | mid | count                                      | Result        |
| ---- | ----- | --- | ------------------------------------------ | ------------- |
| 1    | 8     | 4   | 5 bc the smaller number are  3, 1, 1, 1, 4 | `count > mid` |

New array is `[1, 4]` and 1 is inside that range.:white\_check\_mark:&#x20;
{% endtab %}
{% endtabs %}

{% hint style="info" %}
Maybe think about `[3, 8, 8, 4, 6, 1, 5, 9]`. Length - 1?
{% endhint %}

* Time complexity for this solution is

$$
O(n\log{n})
$$

* Space complexity should be

$$
O(1)
$$

## Solution 2 (Java)

### Notes (Sort)

* Time complexity: O(nlogn)
* Space complexity: O(logn) or O(n), does not meet the requirement for this problem but indeed a solution

## Solution 3 (Java)

### Notes (Set)

* Use a set to find the duplicated number
* If the set already contains a number when adding it, it is the duplicated one.

## Solution 4 (Java)

### Notes (Array as HashMap)

## Solution 5 (Java)

### Notes (Floyd's Algorithm)

* A similar idea as used in [Linked Cycle II](/algo/linked-list/linked-list-cycle-ii).


# Sqrt(x) II

ID: 586; medium; 对x开根II

{% embed url="<https://www.lintcode.com/problem/586/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param x: a double
     * @return: the square root of x
     */
    public double sqrt(double x) {
        double left = 0;
        double right = Math.max(x, 1.0);
        double delta = 1e-12;
        while (left + delta < right) {
            double mid = left + (right - left) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;

    }
}
```

### Notes

* Discuss the cases when `x` is greater than 1 and `x` is less than 1.
* 12 decimal places can be achieved by setting the `delta`/difference between left and right to be `1e-12`.


# Maximum Average Subarray II

ID: 617; medium; 子数组的最大平均值 II

{% embed url="<https://www.lintcode.com/problem/617/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param nums: an array with positive and negative numbers
     * @param k: an integer
     * @return: the maximum average
     */
    public double maxAverage(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) 
            return -1;

        double left, right, mid;
        left = right = nums[0];
        double delta = 1e-6;

        for (int n : nums) {
            left = Math.min(n, left);
            right = Math.max(n, right);
        }

        while (left + delta < right) {
            mid = left + (right - left) / 2;
            if (isAverageValid(nums, mid, k)) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return isAverageValid(nums, right, k) ? right : left;
    }

    private boolean isAverageValid(int[] nums, double avg, int k) {
        double sum = 0, leftSum = 0, leftSumMin = 0;
        for (int i = 0; i < nums.length; i++) {
            // sum is the sum of elements from 0 to i
            sum += nums[i] - avg;
            
            if (i >= k - 1 && sum >= 0) return true;
            if (i >= k) {
                // left sum is the sum of elements from 0 to i-k
                leftSum += nums[i - k] - avg;
                leftSumMin = Math.min(leftSumMin, leftSum);
                // difference here is the max value for a k-length array
                if (sum - leftSumMin >= 0)
                    return true;
            }
        }
        return false;
    }
}
```


# Copy Books

ID: 437; medium; 书籍复印

{% embed url="<https://www.lintcode.com/problem/437/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length == 0 || k <= 0)
            return 0;
        
        int left = 0, right = Integer.MAX_VALUE;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (isTimeFeasible(pages, k, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return isTimeFeasible(pages, k, left) ? left : right;
    }

    private boolean isTimeFeasible(int[] pages, int k, int time) {
        int numOfCopiers = 0, remain = 0;
        for (int page : pages) {
            if (page > time) return false;
            if (page > remain) {
                numOfCopiers++;
                remain = time;
            }
            remain -= page;
        }
        return numOfCopiers <= k;
    }
}
```

### Notes

* The check of a feasible time here is crucial. Given a `time`, how do we know the minimum number of copiers needed to complete the job?
  * If there is one book that takes longer than `time` to be copied, there is no way this `time` is feasible.
  * Else in the general case, count the minimum number of copier needed. If this minimum number is larger than `k`, then the `time` is not feasible.

## Solution 2 (Java)

```java
public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages == null || pages.length == 0 || k <= 0)
            return 0;
        
        int left = pages[0], right = 0, mid;
        for (int page : pages) {
            left = Math.max(left, page);
            right += page;
        }

        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (isTimeFeasible(pages, k, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return isTimeFeasible(pages, k, left) ? left : right;
    }

    private boolean isTimeFeasible(int[] pages, int k, int time) {
        int numOfCopiers = 1, pageSum = 0;
        for (int page : pages) {
            if (page > time) return false;
            if (pageSum + page <= time) {
                pageSum += page;
            } else {
                numOfCopiers++;
                pageSum = page;
            }
        }
        
        return numOfCopiers <= k;
    }
}
```

### Notes

* We can further reduce the initial range by setting `left` to be the maximum page number and `right` to be the sum of the `pages` array. The reason is that the lower bound of the time is achieved by having `k = pages.length` and each person copies one book; the minimum time now would be the time to copy the book with largest page count. Then, the upper bound of the time is achieved by having only 1 copier to copy all the books by himself; so the time would be the sum of all the pages counts.
* Also, this solution uses a slightly different method to determine if time is feasible.


# How Many Problem Can I Accept

ID: 937; medium; 可以完成的题目数量

{% embed url="<https://www.lintcode.com/problem/937/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @param k: an integer
     * @return: how many problem can you accept
     */
    public long canAccept(long n, int k) {
        long left = 0;
        long right = (long) Math.sqrt(2 * n / k);
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if ((findTime(mid, k)) > n) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (findTime(right, k) <= n) return right;
        return left;
    }

    private long findTime(long i, int k) {
        return k * ((1 + i) * i / 2);
    }
}
```

### Notes

$$
\sum\_{i=1}^{x}k \times i \leq n
$$

$$
\frac{x(1+x)}{2} \leq \frac{n}{k} \ \\
$$

$$
x < \sqrt{x^2+x} \leq \sqrt{\frac{2n}{k}}
$$

The search range is `[0, sqrt(2n/k)]`. Normally, we would set `right` to be `n`, but here it would exceed the time limit since `n` is long.


# Linked List


# Insert Node in Sorted Linked List

ID: 219; easy; 在排序链表中插入一个节点

{% embed url="<https://www.lintcode.com/problem/219/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The head of linked list.
     * @param val: An integer.
     * @return: The head of new linked list.
     */
    public ListNode insertNode(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        
        while (cur.next != null && cur.next.val <= val) {
            cur = cur.next;
        }

        ListNode newNode = new ListNode(val);
        newNode.next = cur.next;
        cur.next = newNode;

        return dummy.next;
    }
}
```

### Notes

* Find the first node in the list after which the new node should be inserted.


# Merge Two Sorted Lists

ID: 165; easy; 合并两个排序链表

{% embed url="<https://www.lintcode.com/problem/165/>" %}

{% embed url="<https://leetcode.com/problems/merge-two-sorted-lists/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 == null) cur.next = l2;
        if (l2 == null) cur.next = l1;

        return dummy.next;
    }
}
```


# Merge K Sorted Lists

ID: 104; medium; 合并k个排序链表算法

{% embed url="<https://www.lintcode.com/problem/104/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0)
            return null;
        return mergeHelper(lists, 0, lists.size() - 1);
    }

    private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
        if (start == end) return lists.get(start);
        
        int mid = start + (end - start) / 2;
        ListNode leftHalf = mergeHelper(lists, start, mid);
        ListNode rightHalf = mergeHelper(lists, mid + 1, end);
        return mergeTwoLists(leftHalf, rightHalf);
    }
    
    // from Merge Two Sorted Lists
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 == null) cur.next = l2;
        if (l2 == null) cur.next = l1;
        return dummy.next;
    }
}

```

### Notes

* This solution uses **divide and conquer**.
* Let `k` be the number of lists and `n` be the number of nodes in a list on average, then the time complexity is `O(nk * log(k))`. Also, the recursion uses the stack space, which is `O(n)`.

## Solution 2 (Java)

```java
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0)
            return null;
        
        Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null)
                heap.add(lists.get(i));
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!heap.isEmpty()) {
            ListNode head = heap.poll();
            cur.next = head;
            cur = cur.next;
            if (head.next != null)
                heap.add(head.next);
        }
        return dummy.next;
    }

    private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
        public int compare(ListNode left, ListNode right) {
            return left.val - right.val;
        }
    };
}

```

### Notes

* This solution uses a **minimum heap** with the size of the lists. Each time, we grab a node from each list and add the smallest one to the linked list by the property of the min heap.

## Solution 3 (Java)

```java
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> lists) {  
        if (lists == null || lists.size() == 0)
            return null;
        
        while (lists.size() > 1) {
            List<ListNode> newLists = new ArrayList<ListNode>();
            for (int i = 0; i + 1 < lists.size(); i+=2) {
                ListNode twoMergedLists = mergeTwoLists(lists.get(i), lists.get(i+1));
                newLists.add(twoMergedLists);
            }
            if (lists.size() % 2 == 1) {
                newLists.add(lists.get(lists.size() - 1));
            }
            lists = newLists;
        }

        return lists.get(0);
    }

    // from Merge Two Sorted Lists
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 == null) cur.next = l2;
        if (l2 == null) cur.next = l1;
        return dummy.next;
    }
}

```

### Notes

* This solution is straightforward. We simply merge the lists two by two, which is similar to a playoffs elimination table.
* Be careful if the number of lists is odd.


# LRU Cache

ID: 134; hard; LRU缓存策略

{% embed url="<https://www.lintcode.com/problem/134/>" %}

{% embed url="<https://leetcode.com/problems/lru-cache/>" %}

## Solution 1 (Java)

```java
public class LRUCache {

    class Node {
        int key, val;
        Node next = null;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
        }
    }

    int capacity, size;
    Node dummy, end;
    HashMap<Integer, Node> keyToPrevMap;

    /*
     * @param capacity: An integer
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.dummy = new Node(0, 0);
        this.end = this.dummy;
        this.keyToPrevMap = new HashMap<Integer, Node>();
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        if (!keyToPrevMap.containsKey(key))
            return -1;

        moveToEnd(key);
        return end.val;
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // Case I: replace old key and value
        if (get(key) != -1) {
            Node prev = keyToPrevMap.get(key);
            prev.next.val = value;
            return;
        }

        // Case II: add new key and value when in capacility limit
        if (size < capacity) {
            Node newNode = new Node(key, value);
            end.next = newNode;
            keyToPrevMap.put(key, end);
            end = newNode;
            size++;
            return;
        }

        // Case III: invalidate LRU item and add new key and value
        // 1. remove first/LRU node
        Node firstNode = dummy.next;
        keyToPrevMap.remove(firstNode.key);
        // 2. reuse that first node and move it to the end
        firstNode.key = key;
        firstNode.val = value;
        keyToPrevMap.put(key, dummy);
        moveToEnd(key);
    }

    private void moveToEnd(int key) {
        Node prev = keyToPrevMap.get(key);
        Node curr = prev.next;

        if (curr == end) return;
        prev.next = curr.next;
        end.next = curr;

        // update the map for prev and curr
        if (prev.next != null) {
            keyToPrevMap.put(prev.next.key, prev);
        }
        keyToPrevMap.put(curr.key, end);
        end = curr;
    }
}
```

### Notes

We uses a singly linked list and a hash map in this solution. The linked list is basically the cache, where the head is the least recently used (LRU) and the end is the most recently used.The hash map keeps track of **key** and **previous node** pairs.

* We first define a `Node` class with fields including `key`, `val`, and `next`.
* Then, the fields of the `LRUCache` class includes:
  * `capacity`: the full capacity of the cache as required by user input.
  * `size`: the current size of the cache
  * `dummy`: the dummy node pointing to the head of the linked list
  * `end`: the end of the linked list
  * `keyToPrevMap`: the hash map of `(key, previous node)` pairs.

#### The `get` method

We first check if a node with the input `key` is in the map. If not, we return -1 not found. If we do find a node associated with that key, we move that node to the end of the linked list and return its value. (`moveToEnd` method to be completed later)

#### The `set` method

We have three cases for setting key/value pairs.

1. The key is already contained in the map. All we need to do is find that node and change its value.
2. Within in the capacity limit, we can directly add a new node to the end of the linked list. Do not forget to update the `end`, the `map`, and the `size`.
3. When the capacity limit will be exceeded, we remove the first/LRU node from the `map`. Next, we reuse that first node by putting the new key and value into that node. Then, we move that node to the end of the linked list, meaning that it is the most recently used. Do not forget to update the map as well (for changing the head of the list).

#### The `moveToEnd` method

We take in a `key` and want to move the node associated with that key to the end of the linked list. We first remove it from where it currently is, i.e., pointing its previous node to its next node. Then, we add it at the end of the list. More importantly, do not forget to update the `map` since two positions in the linked list have changed and do not forget to update end as well.

## Solution 2 (Java)

```java
class LRUCache {
    
    class Node {
        int key, val;
        Node prev, next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    int capacity;
    Node head, tail;
    Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        Node curr = map.get(key);
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;
        moveToTail(curr);
        return curr.val;
    }
    
    public void put(int key, int value) {
        if (get(key) != -1) {
            Node curr = map.get(key);
            curr.val = value;
            return;
        }
        
        if (map.size() == capacity) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        moveToTail(newNode);
    }
    
    private void moveToTail(Node curr) {
        curr.prev = tail.prev;
        tail.prev = curr;
        curr.prev.next = curr;
        curr.next = tail;
    }
}

// O <-> O <-> O <-> O <-> O

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
```

### Notes

* Here we used a doubly linked list.
* Note that `head` and `tail` are not actually the head and tail of the doubly linked list. `Head` is the node before the actual head and `tail` is the node after the actual tail of the list.


# Reverse Linked List II

ID: 36; medium; 翻转链表（二）

{% embed url="<https://www.lintcode.com/problem/36/>" %}

{% embed url="<https://leetcode.com/problems/reverse-linked-list-ii/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: ListNode head is the head of the linked list 
     * @param m: An integer
     * @param n: An integer
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        // 1. proceed to m's previous node
        for (int i = 0; i < m - 1; i++) {
            if (cur == null) return null;
            cur = cur.next;
        }

        // 2. reverse from m to n
        ListNode mPrev = cur;
        ListNode mNode = cur.next;
        cur = cur.next;
        ListNode prev = null, next;
        for (int i = m; i <= n; i++) {
            if (cur == null) return null;
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        // 3. connect the lists
        mPrev.next = prev;
        mNode.next = cur;
        return dummy.next;
    }
}
```

### Notes

We have three major steps here:

1. We first proceed to the (m-1)-th node, which is the node before the m-th node. Then we keep track of both of them.
2. We reverse from m to n using the same technique used in the classical [reverse linked list](/algo/linked-list/reverse-linked-list).
3. Lastly, do not forget to connect the middle part, i.e., the reversed linked list, with `mPrev` and `cur` pointer.

```java
m = 2, n = 4;

     mPrev      mNode             n
step1: 1------->2------->3------->4------->5------->6

     mPrev      mNode            prev     cur
step2: 1        2<-------3<-------4        5------->6

     mPrev    prev              mNode     cur
step3: 1------->4------->3------->2------->5------->6
```


# Copy List with Random Pointer

ID: 105; medium; 复制带随机指针的链表

{% embed url="<https://www.lintcode.com/problem/105/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;

        RandomListNode dummy = new RandomListNode(0);
        RandomListNode prev = dummy, newNode;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

        while (head != null) {
            // deal with the core nodes
            if (!map.containsKey(head)) {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            } else {
                newNode = map.get(head);
            }
            prev.next = newNode;

            // deal with random pointers of the core nodes
            if (head.random != null) {
                if (!map.containsKey(head.random)) {
                    newNode.random = new RandomListNode(head.random.label);
                    map.put(head.random, newNode.random);
                } else {
                    newNode.random = map.get(head.random);
                }
            }
            prev = newNode;
            head = head.next;
        }

        return dummy.next;
    }
}
```

### Notes

* This solution uses a HashMap to keep track of the original nodes and their duplicates.
* For each iteration, we first deal with the node itself. If it is not in the HashMap, we add it to the `map` where the key is itself and the value is its duplicate. If it is in the `map`, the next node for the deep copy is its value, i.e., the duplicate in the map. Next, we deal with the random pointers of the node. Using a similar approach, we point the random pointer of the node in the deep copy to a duplicate.
* Do not forget to update `prev` and `head`. Here, `prev` is for constructing the new deep copy and `head` is just for traversing the original linked list.&#x20;
* Time complexity is `O(n)` and space complexity is also `O(n)`.

### **Scratches**

![](/files/-Mbo69KVjmeNBsmIAhjG)

## Solution 2 (Java)

```java
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        copyNext(head);
        copyRandom(head);
        return splitLists(head);
    }

    private void copyNext(RandomListNode head) {
        RandomListNode newNode = null;
        while (head != null) {
            newNode = new RandomListNode(head.label);
            newNode.next = head.next;
            // newNode.random = head.random;
            head.next = newNode;
            head = head.next.next;
        }
    }

    private void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.random != null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }

    private RandomListNode splitLists(RandomListNode head) {
        RandomListNode newHead = head.next;
        while (head != null) {
            RandomListNode duplicate = head.next;
            head.next = head.next.next;
            if (duplicate.next != null) {
                duplicate.next = duplicate.next.next;
            }
            head = head.next;
        }
        return newHead;
    }
}
```

### Notes

* This solution uses three pass to copy the original list. Thus, there are three steps:
  1. copyNext: This step creates new duplicated nodes and point their next pointers to their originals'.
  2. copyRandom: This step simply point the duplicates' random pointers to the corresponding duplicates of their original nodes' random pointers. The key operation here is `head.next.random = head.random.next`. The left is the random pointer of the duplicate and the right is the duplicate of the original random node.
  3. splitLists: We cut the connections between the original list and the new deep copy. Be careful with null checking in the loop to prevent `NullPointerException`.
* The time complexity is still `O(n)`, but the space complexity now is `O(1)`.

### **Scratches**

![](/files/-Mbo6G_E35w0lMdNyn8c)


# Reverse Nodes in k-Group

ID: 450; hard; K组翻转链表

{% embed url="<https://www.lintcode.com/problem/450/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: a ListNode
     * @param k: An integer
     * @return: a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        while (true) {
            cur = reverseBetween(cur, k);
            if (cur == null) break;
        }
        return dummy.next;
    }


    // modified from Reverse Linked List II
    public ListNode reverseBetween(ListNode head, int k) {
        if (head == null) return head;

        // 1. find the k-th node 
        ListNode kNode = head;
        for (int i = 0; i < k; i++) {
            kNode = kNode.next;
            if (kNode == null) return null;
        }

        ListNode firstNode = head.next;
        ListNode kNextNode = kNode.next;

        // 2. reverse
        ListNode prev = null, next;
        ListNode curr = firstNode;
        while (curr != kNextNode) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 3. connect the lists
        head.next = kNode;
        firstNode.next = kNextNode;
        return firstNode;
    }
}
```

### Notes

* We use a similar approach used in [Reverse Linked List II](/algo/linked-list/reverse-linked-list-ii). Using the helper function `reverseBetween`, we reverse `k` nodes each time and return the end of of the linked list for each `k` group. If the end node is null, we know that the remaining nodes cannot constitute a `k` group.
* Inside the helper function, note that the `head` is always one node before the starting node that is to be reversed. Then, we keep track of the first node that is to be reversed (`firstNode`) and the node after k-th node (`kNextNode`) because we need to connect the reversed linked list eventually with a start and an end.


# Add Two Numbers

ID: 2; medium

{% embed url="<https://leetcode.com/problems/add-two-numbers/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{Val: 0}   // dummy node
    val1, val2, carry, runner := 0, 0, 0, head
    for l1 != nil || l2 != nil || carry == 1 {
        if l1 == nil {
            val1 = 0
        } else {
            val1 = l1.Val
            l1 = l1.Next
        }
        if l2 == nil {
            val2 = 0
        } else {
            val2 = l2.Val
            l2 = l2.Next
        }
        runner.Next = &ListNode{Val: (val1 + val2 + carry) % 10}
        carry = (val1 + val2 + carry) / 10
        runner = runner.Next
    }
    return head.Next
}
```

## Solution 2 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int val = (l1.val + l2.val + carry) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            ListNode newNode = new ListNode(val);
            head.next = newNode;
            head = newNode;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 == null && l2 != null)  {
            int val = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            ListNode newNode = new ListNode(val);
            head.next = newNode;
            head = newNode;
            l2 = l2.next;
        }
        while (l2 == null && l1 != null)  {
            int val = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            ListNode newNode = new ListNode(val);
            head.next = newNode;
            head = newNode;
            l1 = l1.next;
        }
        if (carry == 1) head.next = new ListNode(1);
        return dummy.next;
    }
}

//     9 -> 9 -> 9 -> 9
//     9 -> 9
//     8 -> 9 -> 0 -> 0 -> 1
```

## Solution 3 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

// 1111111
//  9999999
//     9999
// 10009998
```


# Swap Nodes in Pairs

ID: 24; medium

{% embed url="<https://leetcode.com/problems/swap-nodes-in-pairs/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first = head;
        ListNode second = head.next;
        ListNode newHead = swapPairs(second.next);
        
        first.next = newHead;
        second.next = first;
        return second;
    }
}
```


# Rotate List

ID: 61; medium

{% embed url="<https://leetcode.com/problems/rotate-list/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0, head);
        k = k % findLengthOfList(head);
        while (k > 0) {
            ListNode secondToLastNode = findSecondToLastNode(dummy.next);
            ListNode lastNode = secondToLastNode.next;
            lastNode.next = dummy.next;
            dummy.next = lastNode;
            secondToLastNode.next = null;
            k--;
        }
        return dummy.next;        
    }
    
    public ListNode findSecondToLastNode(ListNode head) {
        while (head.next.next != null) {
            head = head.next;
        }
        return head;
    }
    
    public int findLengthOfList(ListNode head) {
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }
        return length;
    }
}
```

## Solution 2 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        ListNode runner = head;
        int length = 1;
        while (runner.next != null) {
            runner = runner.next;
            length++;
        }
        
        // runner is the last node now
        runner.next = head;
        // a cycle is formed
        k %= length;
        k = length - k;
        while (k > 0) {
            runner = runner.next;
            k--;
        }
        // find the last node of the new list using k
        head = runner.next;
        runner.next = null;
        return head;
    }
}
```


# Linked List Cycle

ID: 141; easy

{% embed url="<https://leetcode.com/problems/linked-list-cycle/>" %}

{% embed url="<https://www.lintcode.com/problem/102/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    m := make(map[*ListNode]bool)
    for head != nil {
        if _,found := m[head]; found {
            return true
        }
        m[head] = true
        head = head.Next
    }
    return false
}
```

## Solution 2 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    tortoise, hare := head, head
    for tortoise != nil && hare != nil && hare.Next != nil {
        tortoise = tortoise.Next
        hare = hare.Next.Next
        if tortoise == hare {
            return true
        }
    }
    return false
    
}
```

## Solution 3 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }

        return false;
    }
}
```

### Floyd's tortoise and hare cycle-finding algorithm

{% embed url="<https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare>" %}

The tortoise move by 1 step each time and the hare moves by 2 steps at a time. If there is a cycle, the hare will eventually catch the tortoise at a position.

A simple idea of the proof can be tracking the **gap** between the tortoise and the hare. By construction, the gap increases by 1 each iteration. Eventually, the gap with become n, where n is the number of elements in the **cycle** (not the whole list). This is the time when the tortoise and the hare meet. More proofs:

{% embed url="<https://math.stackexchange.com/questions/913499/proof-of-floyd-cycle-chasing-tortoise-and-hare>" %}


# Linked List Cycle II

ID: 142; medium

{% embed url="<https://leetcode.com/problems/linked-list-cycle-ii/>" %}

{% embed url="<https://www.lintcode.com/problem/103/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    m := make(map[*ListNode]bool)
    for head != nil {
        if _,found := m[head]; found {
            return head
        }
        m[head] = true
        head = head.Next
    }
    return nil
}
```

## Solution 2 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    hasCycle, tortoise := hasCycle(head)
    if head == nil || head.Next == nil || !hasCycle {
        return nil
    }
    hare := head
    // both move by 1 and look for second meet
    for tortoise != hare {
        tortoise = tortoise.Next
        hare = hare.Next
    }
    return tortoise
}

// from ID: 141
func hasCycle(head *ListNode) (bool, *ListNode) {
    tortoise, hare := head, head
    for tortoise != nil && hare != nil && hare.Next != nil {
        tortoise = tortoise.Next
        hare = hare.Next.Next
        if tortoise == hare {
            return true, tortoise
        }
    }
    return false, nil
    
}
```

## Solution 3 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;

        ListNode slow = head;
        ListNode fast = head.next;
        
        // slow and fast meet for the first time
        while (slow != fast) {
            if (fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        // the second meeting point is the start of the cycle
        fast = fast.next;
        while (head != fast) {
            head = head.next;
            fast = fast.next;
        }
        return head;
    }

}
```

![Example](/files/-Mal5VcVmlL0_DBGgaAv)

We first use the same algorithm (modified to return the first meeting point) for [problem ID: 141](/algo/linked-list/linked-list-cycle#solution-2). If there is no cycle, we are done and return null. If there is a cycle, we store the first meeting point. From this first meeting point, we set the speed of both the tortoise and the hare to moving by 1 each time. Eventually, they will meet again at the start of the cycle. A quick proof is as follows:

Let `x` be the distance between the `head` and the start of the cycle, `y` be the distance between the start of the cycle to the first meeting point, `z` be the distance between the first meeting point to the start of the cycle. It is clear that `y + z = n`, where `n` is the length of the cycle. Consider the following equations for their first meet:

$$
t\_{tortoise} = \frac{x+y}{1}, \hspace{0.2cm} t\_{hare} = \frac{x+y+z+y}{2}
$$

Because they meet at the first meeting point, their time spent traveling should be the same. Setting the two t's equal to each other, we have `x = z`.

Using this result, we have either one of them start at the `head` of the list and the other continue at their first meeting point (with the same speed now). They will eventually meet at the start of the cycle thanks to the fact `x = z`.


# Intersection of Two Linked Lists

ID: 160; easy

{% embed url="<https://leetcode.com/problems/intersection-of-two-linked-lists/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lengthA, lengthB := getLength(headA), getLength(headB)
    ignore := lengthA - lengthB
    if ignore > 0 {
        for ignore > 0 {
            headA = headA.Next
            ignore--
        }
    } else if ignore < 0 {
        for ignore < 0 {
            headB = headB.Next
            ignore++
        }
    }
    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        if headA.Next == headB.Next {
            return headA.Next
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

func getLength(root *ListNode) int {
    length := 0
    for root != nil {
        length++
        root = root.Next
    }
    return length
}
```

## Solution 2 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    a, b := headA, headB
    // a little bit of trickery
    for a != b {
        if a == nil {
            a = headB
        } else {
            a = a.Next
        }
        if b == nil {
            b = headA
        } else {
            b = b.Next
        }
    }
    return a
}
```

## Solution 3 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA;
        ListNode currB = headB;
        
        while (currA != currB) {
            if (currA == null) {
                currA = headB;
            } else {
                currA = currA.next;
            }
            if (currB == null) {
                currB = headA;
            } else {
                currB = currB.next;
            }
        }
        return currA;
    }
}
```


# Remove Linked List Elements

ID: 203; easy

{% embed url="<https://leetcode.com/problems/remove-linked-list-elements/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        
        ListNode prev = dummy;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}
```

### Notes

* Be careful that we only update `prev` if we do not find a node with matching value and skip that node.


# Reverse Linked List

ID: 206; easy

{% embed url="<https://leetcode.com/problems/reverse-linked-list/>" %}

{% embed url="<https://www.lintcode.com/problem/35/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var before *ListNode
    for head != nil {
        after := head.Next
        head.Next = before
        before = head
        head = after
    }
    return before
}
```

## Solution 2 (Go)

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}
```

## Solution 3 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        ListNode prev = null, next;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
```


# Delete Node in a Linked List

ID: 237; easy

{% embed url="<https://leetcode.com/problems/delete-node-in-a-linked-list/>" %}

## Solution 1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
}
```

## Solution 2

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(node *ListNode) {
    if node == nil {
        return
    }
    runner := node
    for runner.Next.Next != nil {
        runner.Val = runner.Next.Val
        runner = runner.Next
    }
    runner.Val = runner.Next.Val
    runner.Next = nil
}
```


# Odd Even Linked List

ID: 328; medium

{% embed url="<https://leetcode.com/problems/odd-even-linked-list/>" %}

## Solution 1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    oddHead, evenHead := &ListNode{Val: 0}, &ListNode{Val: 0}
    oddRunner, evenRunner, index := oddHead, evenHead, 1
    for head != nil {
        if index % 2 != 0 {
            oddRunner.Next = head
            oddRunner = oddRunner.Next
        } else {
            evenRunner.Next = head
            evenRunner = evenRunner.Next
        }
        index++
        head = head.Next
    }
    oddRunner.Next = evenHead.Next
    evenRunner.Next = nil
    return oddHead.Next
}
```

## Solution 2

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    odd, even := head, head.Next
    evenHead := even
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = evenHead
    return head
}
```


# Partition List

ID: 86; medium

{% embed url="<https://leetcode.com/problems/partition-list/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummySmall = new ListNode(0);
        ListNode dummyLarge = new ListNode(0);
        ListNode headSmall = dummySmall;
        ListNode headLarge = dummyLarge;
        while (head != null) {
            if (head.val < x) {
                headSmall.next = head;
                headSmall = head;
            } else {
                headLarge.next = head;
                headLarge = head;
            }
            head = head.next;
        }
        headSmall.next = dummyLarge.next;
        headLarge.next = null;
        return dummySmall.next;
    }
}
```


# Recursion Basics


# Fibonacci

ID: 366; naive; 斐波纳契数列

{% embed url="<https://www.lintcode.com/problem/366/>" %}

## "Solution 1" (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        if (n <= 1) return 0;
        if (n == 2) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
```

### Notes

* Classical recursion example
* This actually will not pass the test on LintCode (test a relatively large Fibonacci number say the 50th).
* Time complexity: `O(2^n)`, extremely bad exponential runtime.
* Space complexity: `O(1)`, excluding stack space (`O(n)`).

## Solution 2 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        int[] memo = new int[n + 1];
        return fibHelper(n, memo);
    }

    private int fibHelper(int n, int[] memo) {
        if (n <= 1) return 0;
        if (n == 2) return 1;
        if (memo[n] > 0) return memo[n];
        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }
}
```

### Notes

* This solution uses an array to store the Fibonacci values by the concept of **memoization**.&#x20;
* Time complexity: `O(n)`
* Space complexity: `O(n)`

## Solution 3 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        int n1 = 0, n2 = 1, sum = 0;
        for (int i = 1; i < n; i++) {
            sum = n1 + n2;
            n1 = n2;
            n2 = sum;
        }
        return n1;
    }
}
```

### Notes

* This solution also uses the idea of **memoization**, but it uses a constant number of variables to only store the most important information (current 3 numbers).
* `n1`, `n2`, `sum` are the current two numbers and the previous sum of the two numbers.
* Time complexity: `O(n)`
* Space complexity: `O(1)`

## Solution 4 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        int[] fib = new int[]{0, 1, 1};
        for (int i = 3; i < n; i++) {
            fib[i % 3] = fib[(i-1) % 3] + fib[(i-2) % 3];
        }
        return fib[(n-1) % 3];
    }
}
```

### Notes

* This solution is similar to [Solution 2](/algo/recursion-basics/fibonacci#solution-2-java) by using a length-3 array to store the 3 important numbers.
* It is also somewhat different because the third element of the array is indeed the current sum of the first and second elements.
* Time complexity: `O(n)`
* Space complexity: `O(1)`

## Solution 5 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        int[][] fib = new int[][] { { 1, 1 }, { 1, 0 } };
        if (n <= 1) return 0;
        power(fib, n);
        return fib[0][0];
    }

    private void power(int[][] fib, int n) {
        int[][] fibCopy = new int[][] { { 1, 1 }, { 1, 0 } };
        for (int i = 0; i < n - 3; i++) {
            matrixMul(fib, fibCopy);
        }
    }

    private void matrixMul(int[][] fib, int[][] fibCopy) {
        int x = fib[0][0] * fibCopy[0][0] + fib[0][1] * fibCopy[1][0];
        int y = fib[0][0] * fibCopy[0][1] + fib[0][1] * fibCopy[1][1];
        int z = fib[1][0] * fibCopy[0][0] + fib[1][1] * fibCopy[1][0];
        int w = fib[1][0] * fibCopy[0][1] + fib[1][1] * fibCopy[1][1];

        fib[0][0] = x;
        fib[0][1] = y;
        fib[1][0] = z;
        fib[1][1] = w;
    }
}
```

### Notes

$$
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n =
\begin{pmatrix}
F\_{n+1} & F\_n \\
F\_n & F\_{n-1}
\end{pmatrix}
$$

* By the above mathematical rule of Fibonacci numbers, we have this solution.
* Note that the loop does not run for `n = 1, 2, 3` nor any non-positive numbers. So it starts with `n = 4` in the code, but n is actually 2 in the formula and the top-left element would be F3, which is the correct result for the input `n = 4` in the code.
* Time complexity: `O(n)`
* Space complexity: `O(1)`

## Solution 6 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        int[][] fib = new int[][] { { 1, 1 }, { 1, 0 } };
        if (n <= 1) return 0;
        power(fib, n - 2);
        return fib[0][0];
    }

    private void power(int[][] fib, int n) {
        if (n == 0 || n == 1) return;
        int[][] fibCopy = new int[][] { { 1, 1 }, { 1, 0 } };
        power(fib, n / 2);
        matrixMul(fib, fib);

        if (n % 2 != 0) matrixMul(fib, fibCopy);
    }

    private void matrixMul(int[][] fib, int[][] fibCopy) {
        int x = fib[0][0] * fibCopy[0][0] + fib[0][1] * fibCopy[1][0];
        int y = fib[0][0] * fibCopy[0][1] + fib[0][1] * fibCopy[1][1];
        int z = fib[1][0] * fibCopy[0][0] + fib[1][1] * fibCopy[1][0];
        int w = fib[1][0] * fibCopy[0][1] + fib[1][1] * fibCopy[1][1];

        fib[0][0] = x;
        fib[0][1] = y;
        fib[1][0] = z;
        fib[1][1] = w;
    }
}
```

### Notes

* Using the same idea in [Solution 5](/algo/recursion-basics/fibonacci#solution-5-java), we optimize the `power` function by using `divide and conquer`. This idea is also illustrated in this [Pow(x, n)](/algo/math/pow-x-n) problem.
* Time complexity: `O(log n)`
* Space complexity: `O(1)`

This solution can also be extended by deriving a recursive relation from the matrix multiplication. The formula/relation is:&#x20;

* When n is even and k = n / 2,

$$
F(n) = \[2 \times F(k -1) + F(k)] \times F(k)
$$

* When n is even and k = (n+1) / 2,

$$
F(n) = F(k) \times F(k) + F(k-1) \times F(k-1)
$$

* The derivation is shown here:

{% embed url="<https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form>" %}

* This extension would have the same time and space complexity as done in code above. The reason is that this is still essentially **divide and conquer** where `k` is half of `n` each time.

## Solution 7 (Java)

```java
public class Solution {
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        double phi = (1 + Math.sqrt(5)) / 2;
        return (int) Math.round(Math.pow(phi, --n) / Math.sqrt(5));
    }
}
```

### Notes

$$
F(n) = \frac{1}{\sqrt{5}}\[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]
$$

* This solution uses the mathematical formula for calculation (not the recursive relation).
* Note that `n--` because the problem is 1-indexed.&#x20;
* Time complexity: `O(log n)` with the assumption that `Math.pow` takes `log n` time.
* Space complexity: `O(1)`.


# Double Factorial

ID: 771; easy; 二阶阶乘

{% embed url="<https://www.lintcode.com/problem/771/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param n: the given number
     * @return:  the double factorial of the number
     */
    public long doubleFactorial(int n) {
        if (n == 0 || n == 1) return 1;
        return (long)n * doubleFactorial(n - 2);
    }
}
```

### Notes

* By definition of double factorial, the result is immediate.


# Reverse Order Storage

ID: 822; easy; 相反的顺序存储

{% embed url="<https://www.lintcode.com/problem/822/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: the given linked list
     * @return: the array that store the values in reverse order 
     */
    public List<Integer> reverseStore(ListNode head) {
        List<Integer> arr = new ArrayList<Integer>();
        storeHelper(head, arr);
        return arr;
    }

    private void storeHelper(ListNode head, List<Integer> arr) {
        if (head == null) return;
        storeHelper(head.next, arr);
        arr.add(head.val);
    }
}
```


# Linked List Weighted Sum In Reverse Order

ID: 786; easy;

{% embed url="<https://www.lintcode.com/problem/linked-list-weighted-sum-in-reverse-order/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {

    int sum = 0;

    /**
     * @param head: the given linked list
     * @return: the array that store the values in reverse order 
     */
    public int weightedSumReverse(ListNode head) {
        reverseHelper(head);
        return sum;
    }

    private int reverseHelper(ListNode head) {
        if (head == null) return 0;
        int weight = reverseHelper(head.next);
        weight++;
        sum += weight * head.val;
        return weight;
    }
}
```

### Notes

* This is similar to [Reverse Order Storage](/algo/recursion-basics/reverse-order-storage). The difference is that we increment the weight and return it to its upper level each time.


# Binary Tree


# 1. Traversal


# Binary Tree Preorder Traversal

ID: 144; easy

{% embed url="<https://leetcode.com/problems/binary-tree-preorder-traversal/>" %}

{% embed url="<https://www.lintcode.com/problem/66/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    preorderHelper(root, &res)
    return res
}

func preorderHelper(root *TreeNode, res *[]int) {
    if root != nil {
        *res = append(*res, root.Val)
        preorderHelper(root.Left, res)
        preorderHelper(root.Right, res)
    }
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        preorderTraversalHelper(root, result);
        return result;
    }

    private void preorderTraversalHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val);
        preorderTraversalHelper(root.left, result);
        preorderTraversalHelper(root.right, result);
    }
}
```

### Notes

* Recursion / Divide and conquer

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root == null) return result;
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }
}
```

### Notes

* Traversal using a stack


# Binary Tree Inorder Traversal

ID: 94; easy

{% embed url="<https://leetcode.com/problems/binary-tree-inorder-traversal/>" %}

{% embed url="<https://www.lintcode.com/problem/67/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    inorderHelper(root, &result)
    return result
}

func inorderHelper(root *TreeNode, res *[]int) {
    if root != nil {
        inorderHelper(root.Left, res)
        *res = append(*res, root.Val)
        inorderHelper(root.Right, res)
    }
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        inorderTraversalHelper(root, result);
        return result;
    }

    private void inorderTraversalHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        inorderTraversalHelper(root.left, result);
        result.add(root.val);
        inorderTraversalHelper(root.right, result);
    }
}
```

### Notes

* Recursion / Divide and conquer

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }

        return result;
    }
}
```

### Notes

* Traversal


# Binary Tree Postorder Traversal

ID: 145; easy

{% embed url="<https://leetcode.com/problems/binary-tree-postorder-traversal/>" %}

{% embed url="<https://www.lintcode.com/problem/68/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    postorderHelper(root, &res)
    return res
}

func postorderHelper(root *TreeNode, res *[]int) {
    if root != nil {
        postorderHelper(root.Left, res)
        postorderHelper(root.Right, res)
        *res = append(*res, root.Val)
    }
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        postorderTraversalHelper(root, result);
        return result;
    }

    private void postorderTraversalHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        postorderTraversalHelper(root.left, result);
        postorderTraversalHelper(root.right, result);
        result.add(root.val);
    }
}
```

### Notes

* Recursion / Divide and conquer&#x20;

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root == null) return result;
        TreeNode curr = root;
        TreeNode prev = null;
        stack.push(root);

        while (!stack.isEmpty()) {
            curr = stack.peek();
            // traversal down the tree
            if (prev == null || prev.left == curr || prev.right == curr) {
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else if (curr.left == prev) {
                // if the left is visited, visit the right
                if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else { // curr.right == prev
                // if the right is visited, visit the middle
                result.add(curr.val);
                stack.pop();
            }
            prev = curr;
        }

        return result;
    }
}
```

### Notes

* Traversal


# Construct Binary Tree from Inorder and Postorder Traversal

ID: 72; medium; 中序遍历和后序遍历树构造二叉树

{% embed url="<https://www.lintcode.com/problem/72/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inLen = inorder.length;
        int postLen = postorder.length;
        if (inLen == 0 || postLen == 0 || inLen != postLen)
            return null;
        
        int rootVal = postorder[postLen - 1];
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);

        int[] leftNewInorder = Arrays.copyOfRange(inorder, 0, index);
        // left new post order has the same range as above
        int[] leftNewPostorder = Arrays.copyOfRange(postorder, 0, index);
        int[] rightNewInorder = Arrays.copyOfRange(inorder, index + 1, inLen);
        // right new post order excludes the last element (root)
        int[] rightNewPostorder = Arrays.copyOfRange(postorder, index, postLen - 1);

        TreeNode left = buildTree(leftNewInorder, leftNewPostorder);
        TreeNode right = buildTree(rightNewInorder, rightNewPostorder);
        root.left = left;
        root.right = right;
        return root;
    }
}
```

### Notes

1. Find the root of the tree. It should be the last element of the `postorder` array.
2. Find the index of the root in the `inorder` array.
3. The interval \[0, index) of the `inorder` array contains the left subtree, and the interval \[index + 1, inLen) of the `inorder` array contains the right subtree.&#x20;


# Minimum Depth of Binary Tree

ID: 111; easy

{% embed url="<https://leetcode.com/problems/minimum-depth-of-binary-tree/>" %}

{% embed url="<https://www.lintcode.com/problem/155/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Right == nil {
        return minDepth(root.Left) + 1
    }
    if root.Left == nil {
        return minDepth(root.Right) + 1
    }
    return min(minDepth(root.Left), minDepth(root.Right)) + 1
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
    public int minDepth(TreeNode root) {
        if (root == null) 
            return 0;
        if (root.left == null)
            return minDepth(root.right) + 1;
        if (root.right == null)
            return minDepth(root.left) + 1;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        return Math.min(leftDepth, rightDepth) + 1;
    }
}
```

### Notes

* Divide and conquer

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
    public int minDepth(TreeNode root) {
        if (root == null) 
            return 0;
        return minDepthHelper(root);
    }

    private int minDepthHelper(TreeNode root) {
        if (root == null) 
            return Integer.MAX_VALUE;
        if (root.left == null && root.right == null)
            return 1;
        return Math.min(minDepthHelper(root.left), minDepthHelper(root.right)) + 1;

    }
}
```

### Notes

* Divide and conquer slight variant

## Solution 4 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int ans = Integer.MAX_VALUE;

    /**
     * @param root: The root of binary tree
     * @return: An integer
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 1);
        return ans;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            ans = Math.min(ans, depth);
            return;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }


}
```

### Notes

* Traversal


# Find Leaves of Binary Tree

ID: 650; medium; 二叉树叶子顺序遍历

{% embed url="<https://www.lintcode.com/problem/650/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: the root of binary tree
     * @return: collect and remove all leaves
     */
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Integer>> levels = new HashMap<>();

        int maxDepth = dfs(root, levels);
        for (int i = 1; i <= maxDepth; i++) {
            res.add(levels.get(i));
        }
        return res;
    }

    private int dfs(TreeNode root, Map<Integer, List<Integer>> levels) {
        if (root == null) return 0;
        int maxDepth = Math.max(dfs(root.left, levels), dfs(root.right, levels)) + 1;
        // 1 is the bottom level
        levels.putIfAbsent(maxDepth, new ArrayList<>());
        levels.get(maxDepth).add(root.val);
        return maxDepth;
    }
}
```

### Notes

* Use a `HashMap` to store the levels of the tree. The key is the level (1 is the bottom level) and the value of a list of node values.
* Use a similar mechanism in [Maximum Depth of Binary Tree](/algo/binary-tree/2.-classical-questions/maximum-depth-of-binary-tree) and add a few operations to populate the map.&#x20;
* Lastly, convert the values in the map to a result list and return.


# Reconstruct Itinerary

ID: 1288; medium;

{% embed url="<https://www.lintcode.com/problem/1288/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param tickets: 
     * @return: nothing
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            map.putIfAbsent(from, new PriorityQueue<String>());
            map.get(from).offer(to);
        }

        List<String> res = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            String from = stack.peek();
            PriorityQueue<String> tos = map.get(from);
            if (tos == null || tos.isEmpty()) {
                res.add(stack.pop());
                continue;
            }
            stack.push(tos.poll());
        }

        Collections.reverse(res);
        return res;
    }
}
```

### Notes

* Hierholzer's algorithm


# 2. Classical Questions


# Maximum Depth of Binary Tree

ID: 104; easy

{% embed url="<https://leetcode.com/problems/maximum-depth-of-binary-tree/>" %}

{% embed url="<https://www.lintcode.com/problem/97/>" %}

## Solution 1 (Golang)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}
```

### Notes

* &#x20;Recursion with divide and conquer

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    int maxDepth = 0;
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    public int maxDepth(TreeNode root) {
        maxDepthHelper(root, 1);
        return maxDepth;
    }

    private void maxDepthHelper(TreeNode root, int depth) {
        if (root == null) return;
        if (depth > maxDepth) maxDepth = depth;
        
        maxDepthHelper(root.left, depth + 1);
        maxDepthHelper(root.right, depth + 1);
    }
}
```

### Notes

* &#x20;Recursion with traversal


# Average of Levels in Binary Tree

ID: 1115; easy; 二叉树每层的平均数

{% embed url="<https://www.lintcode.com/problem/1115/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the binary tree of the  root
     * @return: return a list of double
     */
    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null) return null;
        List<Double> res = new ArrayList<Double>();
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null)
                    q.offer(node.left);
                if (node.right != null)
                    q.offer(node.right);
            }
            res.add(sum / size);
        }
        return res;
    }
}
```

### Notes

* BFS


# Binary Tree Leaf Sum

ID: 481; easy; 二叉树叶子节点之和

{% embed url="<https://www.lintcode.com/problem/481/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @return: An integer
     */
    public int leafSum(TreeNode root) {
        if (root == null) 
            return 0;

        if (root.left == null && root.right == null)
            return root.val;
            
        return leafSum(root.left) + leafSum(root.right);    
    }
}
```

### Notes

* Divide and conquer

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int sum;

    /**
     * @param root: the root of the binary tree
     * @return: An integer
     */
    public int leafSum(TreeNode root) {
        sum = 0;
        leafSumHelper(root);
        return sum;
    }

    private void leafSumHelper(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            sum += root.val;
            return;
        }
        leafSumHelper(root.left);
        leafSumHelper(root.right);
    }
}
```

### Notes

* Traversal


# Invert Binary Tree

ID: 226; easy

{% embed url="<https://leetcode.com/problems/invert-binary-tree/>" %}

{% embed url="<https://www.lintcode.com/problem/175/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    invertTree(root.Left)
    invertTree(root.Right)
    root.Left, root.Right = root.Right, root.Left
    return root
}
```

\
Solution 2 (Java) <a href="#solution-1-java" id="solution-1-java"></a>
----------------------------------------------------------------------

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void invertBinaryTree(TreeNode root) {
        if (root == null) return;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invertBinaryTree(root.left);
        invertBinaryTree(root.right);
    }
}
```

### Notes

* Recursion

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void invertBinaryTree(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;

            if (curr.left != null)
                q.offer(curr.left);
            if (curr.right != null)
                q.offer(curr.right);
        }
    }
}
```

### Notes

* BFS


# Binary Tree Path Sum

ID: 376; easy;  二叉树的路径和

{% embed url="<https://www.lintcode.com/problem/376/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        List<Integer> path = new ArrayList<>();
        path.add(root.val);
        pathSumHelper(root, path, target, result);
        return result;
    }

    private void pathSumHelper(TreeNode root, List<Integer> path, int target, List<List<Integer>> result) {
        if (root.left == null && root.right == null) {
            if (root.val == target) {
                result.add(new ArrayList<Integer>(path));
            }
            return;
        }

        if (root.left != null) {
            path.add(root.left.val);
            pathSumHelper(root.left, path, target - root.val, result);
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path.add(root.right.val);
            pathSumHelper(root.right, path, target - root.val, result);
            path.remove(path.size() - 1);
        }
    }
}
```


# Binary Tree Path Sum II

ID: 246; medium; 二叉树的路径和 II

{% embed url="<https://www.lintcode.com/problem/246/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        List<Integer> path = new ArrayList<>();
        pathSumHelper(root, target, path, result);
        return result;
    }

    private void pathSumHelper(TreeNode root, int target, List<Integer> path, List<List<Integer>> result) {
        if (root == null) return;
        int sum = 0;
        path.add(root.val);
        for (int i = path.size() - 1; i >= 0; i--) {
            sum += path.get(i);
            if (sum == target) {
                result.add(new ArrayList<Integer>(path.subList(i, path.size())));
            }
        }
        pathSumHelper(root.left, target, path, result);
        pathSumHelper(root.right, target, path, result);
        path.remove(path.size() - 1);
    }
}
```


# Binary Tree Path Sum III

ID: 472; hard; 二叉树的路径和 III

{% embed url="<https://www.lintcode.com/problem/472/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public int val;
 *     public ParentTreeNode parent, left, right;
 * }
 */


public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        List<ParentTreeNode> allNodes = new ArrayList<>();
        inOrderTraversal(root, allNodes);
        for (ParentTreeNode node : allNodes) {
            HashSet<ParentTreeNode> set = new HashSet<>();
            List<Integer> path = new ArrayList<>();
            dfs(node, target, set, path, result);
        }
        return result;
    }

    private void inOrderTraversal(ParentTreeNode root, List<ParentTreeNode> allNodes) {
        if (root == null) return;
        inOrderTraversal(root.left, allNodes);
        allNodes.add(root);
        inOrderTraversal(root.right, allNodes);
    }

    private void dfs(ParentTreeNode root, int target, HashSet<ParentTreeNode> set, List<Integer> path, List<List<Integer>> result) {
        // HashSet to prevent infinite looping
        if (root == null || set.contains(root)) return;
        set.add(root);
        path.add(root.val);
        target -= root.val;
        if (target == 0) {
            List<Integer> pathCopy = new ArrayList<>(path);
            result.add(pathCopy);
        }

        // continue dfs on all directions
        dfs(root.left, target, set, path, result);
        dfs(root.right, target, set, path, result);
        dfs(root.parent, target, set, path, result);

        // reset the variables after done with one node
        set.remove(root);
        path.remove(path.size() - 1);
        target += root.val;
    }
}
```


# Clone Binary Tree

ID: 375; medium; 克隆二叉树

{% embed url="<https://www.lintcode.com/problem/375/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree
     * @return: root of new tree
     */
    public TreeNode cloneTree(TreeNode root) {
        if (root == null) return null;
        TreeNode newNode = new TreeNode(root.val);
        newNode.left = cloneTree(root.left);
        newNode.right = cloneTree(root.right);
        return newNode;
    }
}
```


# Sum Root to Leaf Numbers

ID: 1353; medium; 根节点到叶节点求和

{% embed url="<https://www.lintcode.com/problem/1353/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the tree
     * @return: the total sum of all root-to-leaf numbers
     */
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int num) {
        if (root == null) return 0;
        num = num * 10 + root.val;
        if (root.left == null && root.right == null)
            return num;
        int leftNum = dfs(root.left, num);
        int rightNum = dfs(root.right, num);
        return leftNum + rightNum;
    }
}
```

### Notes

* Divide and conquer

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int sum = 0;

    /**
     * @param root: the root of the tree
     * @return: the total sum of all root-to-leaf numbers
     */
    public int sumNumbers(TreeNode root) {
        if (root == null) return sum;
        dfs(root, root.val);
        return sum;
    }

    private void dfs(TreeNode root, int num) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            sum += num;
            return;
        }
        if (root.left != null)
            dfs(root.left, num * 10 + root.left.val);
        if (root.right != null)
            dfs(root.right, num * 10 + root.right.val);
    }
}
```

### Notes

* Traversal


# Binary Tree Level Sum

ID: 482; easy; 二叉树的某层节点之和

{% embed url="<https://www.lintcode.com/problem/482/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @param level: the depth of the target level
     * @return: An integer
     */
    public int levelSum(TreeNode root, int level) {
        int sum = 0;
        if (root == null || level == 0) return sum;
        return bfs(root, sum, level);
    }

    private int bfs(TreeNode root, int sum, int level) {
        List<Integer> result = new ArrayList<>();
        result.add(root.val);
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (level > 1 && !q.isEmpty()) {
            int size = q.size();
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (curr.left != null) {
                    levelSum += curr.left.val;
                    q.offer(curr.left);
                }
                if (curr.right != null) {
                    levelSum += curr.right.val;
                    q.offer(curr.right);
                }
            }
            result.add(levelSum);
            level--;
        }
        return result.get(result.size() - 1);
    }
}
```

### Notes

* BFS

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @param level: the depth of the target level
     * @return: An integer
     */
    public int levelSum(TreeNode root, int level) {
        int sum = 0;
        if (root == null || level == 0) return sum;
        return bfs(root, sum, level);
    }

    private int bfs(TreeNode root, int sum, int level) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            int levelSum = 0;
            level--;
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                if (level == 0)
                    levelSum += curr.val;
                if (curr.left != null)
                    q.offer(curr.left);
                if (curr.right != null)
                    q.offer(curr.right);
            }
            if (level == 0) return levelSum;
        }
        return sum;
    }
}
```

### Notes

* Optimized BFS


# Binary Tree Paths

ID: 257; easy

{% embed url="<https://leetcode.com/problems/binary-tree-paths/>" %}

{% embed url="<https://www.lintcode.com/problem/480/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "strconv"

func binaryTreePaths(root *TreeNode) []string {
    if root == nil {
        return []string{}
    }
    if root.Left == nil && root.Right == nil {
        return []string{strconv.Itoa(root.Val)}
    }
    result := make([]string, 0)
    leftPaths := binaryTreePaths(root.Left)
    for _,lp := range leftPaths {
        result = append(result, strconv.Itoa(root.Val) + "->" + lp)
    }
    rightPaths := binaryTreePaths(root.Right)
    for _,rp := range rightPaths {
        result = append(result, strconv.Itoa(root.Val) + "->" + rp)
    }
    return result
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;
        dfs(root, String.valueOf(root.val), result);
        return result;
    }

    private void dfs(TreeNode root, String path, List<String> result) {
        if (root == null) return;
        if (root.left == null && root.right == null)
            result.add(path);
        if (root.left != null)
            dfs(root.left, path + "->" + root.left.val, result);
        if (root.right != null)
            dfs(root.right, path + "->" + root.right.val, result);
    }
}
```

### Notes

* This solution computes paths as strings, which is shorter and perhaps more straightforward to understand.

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of the binary tree
     * @return: all root-to-leaf paths
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<TreeNode> path = new ArrayList<>();
        path.add(root);
        dfs(root, path, result);
        return result;
    }

    private void dfs(TreeNode root, List<TreeNode> path, List<String> result) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            String str = "";
            for (int i = 0; i < path.size(); i++) {
                if (i > 0) str += "->";
                str += path.get(i).val;
            }
            result.add(str);
            return;
        }
        path.add(root.left);
        dfs(root.left, path, result);
        path.remove(path.size() - 1);

        path.add(root.right);
        dfs(root.right, path, result);
        path.remove(path.size() - 1);
    }
}
```

### Notes

* This solution computes paths as paths, which is a similar approach used in [Binary Tree Path Sum](/algo/binary-tree/2.-classical-questions/binary-tree-path-sum).


# 3. Binary Search Tree


# Insert Node in a Binary Search Tree

ID: 85; easy; 在二叉查找树中插入节点

{% embed url="<https://www.lintcode.com/problem/85/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        if (root == null)
            return node;
        if (node.val < root.val) {
            root.left = insertNode(root.left, node);
        } else {
            root.right = insertNode(root.right, node);
        }
        return root;
    }
}
```


# Remove Node in Binary Search Tree

ID: 87; hard; 删除二叉查找树的节点

{% embed url="<https://www.lintcode.com/problem/87/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    public TreeNode removeNode(TreeNode root, int value) {
        if (root == null)
            return root;
        if (value < root.val) {
            root.left = removeNode(root.left, value);
        } else if (value > root.val) {
            root.right = removeNode(root.right, value);
        } else {
            if (root.left == null && root.right == null)
                return null;
            if (root.left == null)
                return root.right;
            if (root.right == null)
                return root.left;
            
            int predecessor = findPred(root.left);
            root.val = predecessor;
            root.left = removeNode(root.left, predecessor);
        }
        return root;
    }

    private int findPred(TreeNode root) {
        if (root.right == null) 
            return root.val;
        return findPred(root.right);
    }
}
```

### Notes

First, we use the property of the binary search tree to find the value-matching node. If we find that node, then we have 4 cases:

1. The node is a leaf node. We can directly delete it.
2. The node has one right child, we delete it by returning its right child.
3. The node has one left child, we delete it by returning its left child.
4. The node has two children. We find its predecessor node, which is the node that has the maximum value that is less than the node's value. We replace the node with its predecessor and remove the old position of its predecessor. Here, we can also use successor, which is the node that has the minimum value that is larger then the nodes' value.


# Validate Binary Search Tree

ID: 98; medium; 验证二叉查找树

{% embed url="<https://leetcode.com/problems/validate-binary-search-tree/>" %}

{% embed url="<https://www.lintcode.com/problem/95/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBSTHelper(TreeNode root, long min, long max) {
        if (root == null)
            return true;
        if (root.val <= min || root.val >= max)
            return false;
        boolean isLeftValid = isValidBSTHelper(root.left, min, root.val);
        boolean isRightValid = isValidBSTHelper(root.right, root.val, max);
        return isLeftValid && isRightValid;
    }
}
```


# Trim a Binary Search Tree

ID: 701; medium; 修剪二叉搜索树

{% embed url="<https://www.lintcode.com/problem/701/>" %}

{% embed url="<https://leetcode.com/problems/trim-a-binary-search-tree/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: given BST
     * @param minimum: the lower limit
     * @param maximum: the upper limit
     * @return: the root of the new tree 
     */
    public TreeNode trimBST(TreeNode root, int minimum, int maximum) {
        if (root == null)
            return null;

        if (root.val < minimum)
            return trimBST(root.right, minimum, maximum);
        if (root.val > maximum)
            return trimBST(root.left, minimum, maximum);

        root.left = trimBST(root.left, minimum, maximum);
        root.right = trimBST(root.right, minimum, maximum);
        return root;
    }
}
```


# Search Range in Binary Search Tree

ID: 11; medium; 二叉查找树中搜索区间

{% embed url="<https://www.lintcode.com/problem/11/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private List<Integer> res;
    
    /**
     * @param root: param root: The root of the binary search tree
     * @param k1: An integer
     * @param k2: An integer
     * @return: return: Return all keys that k1<=key<=k2 in ascending order
     */
    public List<Integer> searchRange(TreeNode root, int k1, int k2) {
        res = new ArrayList<Integer>();
        searchRangeHelper(root, k1, k2);
        return res;
    }

    private void searchRangeHelper(TreeNode root, int k1, int k2) {
        if (root == null)
            return;

        // similar to inorder traversal to ensure ascending order
        if (root.val > k1)
            searchRangeHelper(root.left, k1, k2);
        if (root.val >= k1 && root.val <= k2)
            res.add(root.val);
        if (root.val < k2)
            searchRangeHelper(root.right, k1, k2);
    }
}
```


# Inorder Successor in BST

ID: 448; medium; 二叉查找树的中序后继

{% embed url="<https://www.lintcode.com/problem/448/>" %}

## Solution 1 (Java)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


public class Solution {

    TreeNode successor = null;

    /*
     * @param root: The root of the BST.
     * @param p: You need find the successor node of p.
     * @return: Successor of p.
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root, p);
        return successor;
    }

    private void dfs(TreeNode root, TreeNode p) {
        if (root == null || p == null)
            return;
        if (p.val >= root.val) {
            dfs(root.right, p);
        } else {
            successor = root;
            dfs(root.left, p);
        }
    }
}
```

### Notes

* Recursion

## Solution 2 (Java)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the BST.
     * @param p: You need find the successor node of p.
     * @return: Successor of p.
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }
}
```

### Notes

* Traversal


# Binary Search Tree Iterator

ID: 86; hard; 二叉查找树迭代器

{% embed url="<https://www.lintcode.com/problem/86/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = new BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode node = iterator.next();
 *    do something for node
 * } 
 */


public class BSTIterator {

    private Deque<TreeNode> stack;
    private TreeNode next;
    /**
    * @param root: The root of binary tree.
    */
    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<TreeNode>();
        next = root;
    }

    /**
     * @return: True if there has next node, or false
     */
    public boolean hasNext() {
        if (next != null) {
            TreeNode curr = next;
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            next = null;
        }
        return !stack.isEmpty();
    }

    /**
     * @return: return next node
     */
    public TreeNode next() {
        if (!hasNext())
            return null;
        TreeNode curr = stack.pop();
        next = curr.right;
        return curr;
    }
}
```

### Notes

* Use stack to store all the left children.&#x20;
* If the stack is empty, then there is no next node.
* The top of the stack is the current node. In terms of the tree structure, the next node of the current node is its right child.


# Recover Binary Search Tree

ID: 691; medium; 恢复二叉搜索树

{% embed url="<https://www.lintcode.com/problem/691/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the given tree
     * @return: the tree after swapping
     */
    public TreeNode bstSwappedNode(TreeNode root) {
        // nodes inorder should be non-decreasing
        List<TreeNode> nodes = new ArrayList<>();
        inorderTraversal(root, nodes);

        TreeNode firstWrongNode = null, secondWrongNode = null;
        for (int i = 1; i < nodes.size(); i++) {
            if (nodes.get(i).val < nodes.get(i - 1).val) {
                if (firstWrongNode == null)
                    firstWrongNode = nodes.get(i - 1);
                secondWrongNode = nodes.get(i);
            }
        }

        if (firstWrongNode != null) {
            int temp = firstWrongNode.val;
            firstWrongNode.val = secondWrongNode.val;
            secondWrongNode.val = temp;
        }

        return root;
    }

    private void inorderTraversal(TreeNode root, List<TreeNode> nodes) {
        if (root == null)
            return;
        inorderTraversal(root.left, nodes);
        nodes.add(root);
        inorderTraversal(root.right, nodes);
    }
}
```

### Notes

* Use [inorder traversal](/algo/binary-tree/1.-traversal/binary-tree-inorder-traversal) and put the nodes into a list.
* The list should be in non-decreasing order by construction. Iterate the list to find the node that is smaller than its previous node, then swap these two nodes.
* Space complexity is `O(n)`

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    TreeNode first = null, second = null, prev = null;

    /**
     * @param root: the given tree
     * @return: the tree after swapping
     */
    public TreeNode bstSwappedNode(TreeNode root) {
        prev = new TreeNode(Integer.MIN_VALUE);
        inorderTraversal(root);

        if (first != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
        return root;
    }

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

        inorderTraversal(root.left);
        if (root.val < prev.val) {
            if (first == null)
                first = prev;
            second = root;
        }
        prev = root;
        inorderTraversal(root.right);
    }
}
```

### Notes

* We still use [inorder traversal](/algo/binary-tree/1.-traversal/binary-tree-inorder-traversal) but modify it to check if we have any out-of-order nodes (the two nodes that are not in non-decreasing order).
* Space complexity is `O(1)`


# 4. Divide and Conquer


# Balanced Binary Tree

ID: 110; easy

{% embed url="<https://leetcode.com/problems/balanced-binary-tree/>" %}

{% embed url="<https://www.lintcode.com/problem/93/>" %}

## Solution 1 (Go)

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    leftDepth := depthHelper(root.Left)
    rightDepth := depthHelper(root.Right)
    if abs(leftDepth - rightDepth) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func depthHelper(root *TreeNode) int {
    if root == nil {
        return 0
    } 
    return max(depthHelper(root.Left), depthHelper(root.Right)) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func abs(x int) int {
    if x >= 0 {
        return x
    }
    return -x
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        
        int leftDepth = depthHelper(root.left);
        int rightDepth = depthHelper(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1)
            return false;

        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int depthHelper(TreeNode root) {
        if (root == null)
            return 0;
        
        int left = depthHelper(root.left);
        int right = depthHelper(root.right);
        return Math.max(left, right) + 1;
    }
}
```

## Solution 3 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private boolean balanced = true;
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        depthHelper(root);
        return balanced;
    }

    private int depthHelper(TreeNode root) {
        if (root == null)
            return 0;
        
        int left = depthHelper(root.left);
        int right = depthHelper(root.right);
        if (Math.abs(left - right) > 1)
            balanced = false;
            
        return Math.max(left, right) + 1;
    }
}
```

### Notes

* The refactored version of [Solution 2](/algo/binary-tree/4.-divide-and-conquer/balanced-binary-tree#solution-2-java).
* Solution 2 should be easier to follow and understand.


# Minimum Subtree

ID: 596; easy; 最小子树

{% embed url="<https://www.lintcode.com/problem/596/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int sum = Integer.MAX_VALUE;
    private TreeNode node = null;

    /**
     * @param root: the root of binary tree
     * @return: the root of the minimum subtree
     */
    public TreeNode findSubtree(TreeNode root) {
        findSubtreeHelper(root);
        return node;
    }

    private int findSubtreeHelper(TreeNode root) {
        if (root == null)
            return 0;
        
        int currSum = root.val + findSubtreeHelper(root.left) + findSubtreeHelper(root.right);
        if (currSum <= sum) {
            sum = currSum;
            node = root;
        }
        return currSum;
    }
}
```


# Subtree with Maximum Average

ID: 597; easy

{% embed url="<https://www.lintcode.com/problem/597/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private class Result {
        int sum, num;
        public Result(int sum, int num) {
            this.sum = sum;
            this.num = num;
        }
    }

    private TreeNode maxAvgNode = null;
    private Result maxAvg = null;

    /**
     * @param root: the root of binary tree
     * @return: the root of the maximum average of subtree
     */
    public TreeNode findSubtree2(TreeNode root) {
        if (root == null)
            return null;
        dfs(root);
        return maxAvgNode;
    }

    private Result dfs(TreeNode root) {
        if (root == null)
            return new Result(0, 0);

        Result left = dfs(root.left);
        Result right = dfs(root.right);
        Result rootResult = new Result(left.sum + right.sum + root.val, left.num + right.num + 1);
        if (maxAvgNode == null || rootResult.sum * maxAvg.num > maxAvg.sum * rootResult.num) {
            maxAvg = rootResult;
            maxAvgNode = root;
        }
        return rootResult;
    }
}
```


# Maximum Subtree

ID: 628; easy

{% embed url="<https://www.lintcode.com/problem/628/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int sum = Integer.MIN_VALUE;
    private TreeNode node = null;

    /**
     * @param root: the root of binary tree
     * @return: the maximum weight node
     */
    public TreeNode findSubtree(TreeNode root) {
        findSubtreeHelper(root);
        return node;
    }

    private int findSubtreeHelper(TreeNode root) {
        if (root == null)
            return 0;
        
        int left = findSubtreeHelper(root.left);
        int right = findSubtreeHelper(root.right);
        int currSum = root.val + left + right;
        if (currSum >= sum) {
            sum = currSum;
            node = root;
        }
        return currSum;
    }
}
```

### Notes

* Almost the same as [Minimum Subtree](/algo/binary-tree/4.-divide-and-conquer/minimum-subtree).


# Lowest Common Ancestor of a Binary Tree

ID: 88; medium

{% embed url="<https://www.lintcode.com/problem/88/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null)
            return null;
        if (root == A || root == B)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null)
            return root;
        if (left != null)
            return left;
        if (right != null)
            return right;
        
        return null;
    }
}
```

### Notes

There are 4 general cases.

1. If `root` is `A` or `B`, we directly return the root since both `A` and `B` are guaranteed to be in the tree. If the `root` is one of them, then the other one must be its descendent.
2. If `A` and `B` are on the different sides of the `root`, then the `root` of the LCA.
3. If `A` and `B` are both in the left tree, then we find the LCA of the left tree.
4. If `A` and `B` are both in the right tree, then we find the LCA of the right tree.


# Lowest Common Ancestor II

ID: 474; easy

{% embed url="<https://www.lintcode.com/problem/474/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */


public class Solution {
    /*
     * @param root: The root of the tree
     * @param A: node in the tree
     * @param B: node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        List<ParentTreeNode> pathA = retrace(A);
        List<ParentTreeNode> pathB = retrace(B);
        int indexA = pathA.size() - 1;
        int indexB = pathB.size() - 1;

        ParentTreeNode lca = null;

        while(indexA >= 0 && indexB >= 0) {
            if (pathA.get(indexA) != pathB.get(indexB))
                break;
            lca = pathA.get(indexA);
            indexA--;
            indexB--;
        }

        return lca;
    }

    private List<ParentTreeNode> retrace(ParentTreeNode node) {
        List<ParentTreeNode> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        return path;
    }
}

// pathA: 3 4
// pathB: 5 7 4

// pathA: 5 7 4
// pathB: 6 7 4
```

### Notes

* This solution is straight-forward. We first find the path of the `A` and `B` nodes by retracing from their parent nodes.
* We compare these two paths from the last elements. The last element that the two paths share is the least common ancestor of `A` and `B`.


# Lowest Common Ancestor III

ID: 578; medium

{% embed url="<https://www.lintcode.com/problem/578/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {

    private class Result {
        public boolean hasA, hasB;
        public Result(boolean hasA, boolean hasB) {
            this.hasA = hasA;
            this.hasB = hasB;
        }
    }

    private TreeNode res = null;

    /*
     * @param root: The root of the binary tree.
     * @param A: A TreeNode
     * @param B: A TreeNode
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        dfs(root, A, B);
        return res;
    }

    private Result dfs(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null)
            return new Result(false, false);
        
        Result left = dfs(root.left, A, B);
        Result right = dfs(root.right, A, B);

        boolean a = left.hasA || right.hasA || root == A;
        boolean b = left.hasB || right.hasB || root == B;

        if (a && b && res == null)
            res = root;

        return new Result(a, b);
    }
}
```

### Notes

* We use the `Result` class to keep track of the status of `A` and `B` in the tree.
* If `a` and `b` are both `true`, which means the current `root` is already is LCA, then we set `res` only when it is null. This if statement is `true` for the LCA and its ancestors, but we are guaranteed to have the LCA. The reason is that we are doing a DFS and the LCA appears first. Once we set `res` to the LCA, we do not update it and do not care about its ancestors.


# Binary Tree Maximum Path Sum II

ID: 475; medium

{% embed url="<https://www.lintcode.com/problem/475/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of binary tree.
     * @return: An integer
     */
    public int maxPathSum2(TreeNode root) {
        if (root == null)
            return 0;
        
        int leftSum = maxPathSum2(root.left);
        int rightSum = maxPathSum2(root.right);
        int leftOrRight = Math.max(leftSum + root.val, rightSum + root.val);
        return Math.max(root.val, leftOrRight);
    }
}
```

## Solution 2 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private class SumNode {
        public TreeNode node;
        public int sum;
        public SumNode(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }

    /**
     * @param root: the root of binary tree.
     * @return: An integer
     */
    public int maxPathSum2(TreeNode root) {
        if (root == null)
            return 0;
        
        int ans = Integer.MIN_VALUE;
        Queue<SumNode> q = new ArrayDeque<>();
        q.offer(new SumNode(root, root.val));
        while (!q.isEmpty()) {
            SumNode curr = q.poll();
            if (curr.sum > ans)
                ans = curr.sum;
            if (curr.node.left != null)
                q.offer(new SumNode(curr.node.left, curr.sum + curr.node.left.val));
            if (curr.node.right != null)
                q.offer(new SumNode(curr.node.right, curr.sum + curr.node.right.val));
        }
        return ans;
    }
}
```

### Notes

* Non-recursive version using a queue.


# Binary Tree Maximum Path Sum

ID: 94; medium

{% embed url="<https://www.lintcode.com/problem/94/>" %}

## Solution 1 (Java)

```java
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {

    private int maxPathSum = Integer.MIN_VALUE;

    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxPathSum;
    }

    private int dfs(TreeNode root) {
        if (root == null)
            return 0;
        
        int left = dfs(root.left);
        int right = dfs(root.right);

        maxPathSum = Math.max(maxPathSum, left + root.val);
        maxPathSum = Math.max(maxPathSum, right + root.val);
        maxPathSum = Math.max(maxPathSum, root.val);
        maxPathSum = Math.max(maxPathSum, left + right + root.val);

        return Math.max(Math.max(left, right), 0) + root.val;
    }
}
```

### Notes

There are 4 types of paths that can be candidates for the maximum path sum.

1. Max path of left tree + root
2. Max path of right tree + root
3. Only the root
4. Max single path of left tree + root + max single path of right tree


# Path Sum III

ID: 437; medium

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

## Solution 1 (Java)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null)
                return 0;
        
        return pathSum(root.left, targetSum) 
            + pathSum(root.right, targetSum) + findPath(root, targetSum);
    }
    
    private int findPath(TreeNode root, int targetSum) {
        if (root == null)
            return 0;
        
        int res = 0;
        if (root.val == targetSum)
            res += 1;
        res += findPath(root.left, targetSum - root.val);
        res += findPath(root.right, targetSum - root.val);
        return res;
    }
}
```

### Notes

* `pathSum` returns the number of paths that have their sum equal to `targetSum` in the tree rooted at `root`. This include paths that starts at `root` and paths that do not start at `root`.
* `findPath` return the number of paths that have their sum equal to `targetSum`, but the paths must start at `root`.


# Convert Sorted Array to Binary Search Tree

ID; 108; easy

{% embed url="<https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/>" %}

## Solution 1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    n := TreeNode{
        Val: nums[len(nums)/2],
        Left: sortedArrayToBST(nums[:len(nums)/2]),
        Right: sortedArrayToBST(nums[len(nums)/2+1:]),
    }
    return &n
}
```


# Path Sum

ID: 112; easy

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

## Solution 1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }
    curVal := targetSum - root.Val
    return hasPathSum(root.Left, curVal) || hasPathSum(root.Right, curVal)
}
```


# Lowest Common Ancestor of a Binary Search Tree

ID: 235; easy

{% embed url="<https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/>" %}

## Solution 1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || p == nil || q == nil {
        return nil
    }
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}
```


# Sum of Left Leaves

ID: 404; easy

{% embed url="<https://leetcode.com/problems/sum-of-left-leaves/>" %}

## Solution 1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        return root.Left.Val + sumOfLeftLeaves(root.Right)
    }
    return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
```


# Minimum Absolute Difference in BST

ID: 530; easy

{% embed url="<https://leetcode.com/problems/minimum-absolute-difference-in-bst/>" %}

## Solution 1

```go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

func getMinimumDifference(root *TreeNode) int {
    result, previous := math.MaxInt16, -1
    getMinDiffHelper(root, &result, &previous)
    return result
}

func getMinDiffHelper(root *TreeNode, res, prev *int) {
    if root == nil {
        return
    }
    getMinDiffHelper(root.Left, res, prev)
    if *prev != -1 {
        *res = min(*res, abs(root.Val - *prev))
    }
    *prev = root.Val
    getMinDiffHelper(root.Right, res, prev)
}

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

func abs(x int) int {
    if x >= 0 {
        return x
    }
    return -x
}
```

{% hint style="info" %}
Keep track of the previous node. Similar to an inorder traversal.
{% endhint %}




---

[Next Page](/llms-full.txt/1)