二叉树.md

# 二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

这里就我们就来看看，面试中会怎么样来考察我们有关二叉树的问题，首先我们先定义一个节点类：

> 后文测试所使用的节点类如下：
> ps：解释 `LeetCode` 上那种
> ```
> class TreeNode {
>    public TreeNode left, right;
>    public int val;
>
>    public TreeNode(int val) {
>        this.val = val;
>    }
>}
> ```

----

### 顺序遍历 ⭐️⭐️⭐️⭐️

二叉树的遍历分为以下三种：

- 先序遍历：遍历顺序规则为【根左右】

- 中序遍历：遍历顺序规则为【左根右】

- 后序遍历：遍历顺序规则为【左右根】

![顺序遍历](https://user-gold-cdn.xitu.io/2019/10/11/16db82e966bd9fba?w=381&h=282&f=jpeg&s=13263)
下面以上图为例，我们通过代码实现三种基本遍历：

##### 先序遍历：

首先是代码实现：

```java
// 先序遍历
public void preTraverse(TreeNode root) {
    if (root != null) {
        System.out.println(root.val);
        preTraverse(root.left);
        preTraverse(root.right);
    }
}
```

遍历结果：ABCDEFGHK

##### 中序遍历：

首先是代码实现：

```java
// 中序遍历
public void inTraverse(TreeNode root) {
    if (root != null) {
        inTraverse(root.left);
        System.out.println(root.val);
        inTraverse(root.right);
    }
}
```

遍历结果：BDCAEHGKF

##### 后序遍历：

首先是代码实现：

```java
// 后序遍历
public void postTraverse(TreeNode root) {
    if (root != null) {
        postTraverse(root.left);
        postTraverse(root.right);
        System.out.println(root.val);
    }
}
```

遍历结果：DCBHKGFEA

-  视频

[一节课搞定计算机二级难题：二叉树遍历结构](https://www.bilibili.com/video/av44373042?from=search&seid=16041416726295135207)

<br>
<br>

----

#### 

### 层次遍历 - [二叉树的层次遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

二叉树的层次遍历很好理解，在这里我举个例子。首先我们先给出一棵二叉树：

![层次遍历](https://user-gold-cdn.xitu.io/2019/10/11/16db82e995e48ec3?w=359&h=208&f=png&s=4451)

层次遍历顾名思义，就是从上到下，逐层遍历，每层从左往右输出

计算结果：5 - 4 - 8 - 11 - 13 - 4 - 7 - 2 - 1

> 关于遍历算法，常见的有：
> - 深度优先遍历（DFS）
> - 广度优先遍历（BFS）
> <br>
> 
> 在我刷题的过程中遇到过这样一道题：
> - `Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).`
> 
> 即 Z 字型遍历，所以这里再加上一种：
> 
> - Z 字形遍历

下面我们来看看代码上的实现：

#### 深度优先遍历（DFS）⭐️⭐️⭐️⭐️

我们所学的层次遍历只有 BFS（广搜），DFS 深搜本身是用于顺序排序的非递归实现。‘用DFS’ 来解决层次遍历这种题我也是第一次见。

它的步骤可以简要概括为：

1. 常规深度搜索，记录下当前节点所在层 level

2. 将当前节点加入  List 中对应的层

3. 由于是从左往右搜索，所以也是从左往右加入

4. 最后得到一个类似下面的结构

0 -- 5
1 -- 4  -> 8
2 -- 11 -> 13 - > 4
3 -- 7  -> 2 -> 1

> 这种遍历方式太少见，找不到相关的视频，好在原理容易理解

```java
// 层次遍历(DFS)
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    dfs(root, res, 0);
    return res;
}

private void dfs(TreeNode root, List<List<Integer>> res, int level) {
    if (root == null) {
        return;
    }
    if (level == res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(level).add(root.val);
    
    dfs(root.left, res, level + 1);
    dfs(root.right, res, level + 1);
}
```

#### 广度优先遍历（BFS）⭐️⭐️⭐️⭐️

与 DFS 用递归去实现不同，BFS需要用队列去实现。

层次遍历的步骤是：

1. 对于不为空的结点，先把该结点加入到队列中

2. 从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中

3. 重复以上操作直到队列为空

> 说白了就是：`父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可`

-  视频

[二叉树的遍历算法--层次遍历算法](https://www.bilibili.com/video/av35339967?from=search&seid=17612248198253405365)

```java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList();

    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();//返回第一个元素，并在队列中删除
            level.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }

    return result;
}
```

> 1. queue.poll();         //返回第一个元素，并在队列中删除
> 2. queue.element()); //返回第一个元素 
> 3. queue.peek());     //返回第一个元素 
> 4. queue.offer("a"); //添加元素
> 5. add()和remove()  //方法在失败的时候会抛出异常(不推荐)

#### Z 字形遍历 ★★★

这个题型也很罕见，源于 LeetCode 上一道面试原题：

`Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).`给定一棵二叉树，从顶向下，进行Z字形分层遍历，即：如果本层是从左向右的，下层就是从右向左。([103. 二叉树的锯齿形层次遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/))

流程与 BFS 类似，就是多了个用于区分左右的 flag

1. 对于不为空的结点，先把该结点加入到队列中

2. 从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中

3. 将 isFromLeft 值取反

4. 重复以上操作直到队列为空

- 视频

> 同样的这个体型太特殊，所以没有相关视频解析，不过好在算法过程也很好理解

```java
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null){
        return result;
    }
    
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    boolean isFromLeft = false;
    while(!queue.isEmpty()){
        int size = queue.size();
        isFromLeft = !isFromLeft;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node;
            if (isFromLeft){
                node = queue.pollFirst();
            }else{
                node = queue.pollLast();
            }
            list.add(node.val);
            
            if (isFromLeft){
                if (node.left != null){
                    queue.offerLast(node.left);
                }
                if (node.right != null){
                    queue.offerLast(node.right);
                }
            }else{
                if (node.right != null){
                    queue.offerFirst(node.right);
                }
                if (node.left != null){
                    queue.offerFirst(node.left);
                }
            }
        }
        result.add(list);
    }
    
    return result;
}
```

<br>
<br>

----


### ![ABC 字母组合](https://www.bilibili.com/video/av92966020)

- ABC 三个字母所有组合方式？
- ![image-20200409102342821](/Users/huangyuanhao/Library/Application Support/typora-user-images/image-20200409102342821.png)

- 思路：dfs
- 代码

```java
    @Test
    public void test() {
    	dfs(new char[]{'A','B','C'}, new boolean[] {false, false,false}, 0, new ArrayList<Character>());
    }
    
    private void dfs(char[] value, boolean[] flag, int level, ArrayList<Character> res) {
		if (level == value.length) {
			System.out.println(res.toString());
			return;
		}
		
		for (int i = 0; i < flag.length; i++) {
			char c = value[i];
			if (!flag[i]) {
				res.add(c);
				flag[i] = true;
				dfs(value, flag, level + 1, res);
				res.remove(res.size()-1);
				flag[i] = false;
			}
		}
	}
```



#### 

### [复原IP地址](https://leetcode-cn.com/problems/restore-ip-addresses/)

- 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

- 示例:

```java
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
```

- 代码：

```java
    @Test
    public void test() {
    	dfs("19216801", -1, 1, new ArrayList<String>());
    }
    
    private void dfs(String str, int index, int level, ArrayList<String> res) {
		if (level == 5 || index == str.length() - 1) {
			if (level == 5 && index == str.length() - 1) {
				System.out.println(res.toString());
			}
		}
		for (int i = 1; i < 4; i++) {
			if (index + 1+ i > str.length()) {
				continue;
			}
			String x = str.substring(index + 1, index + 1 + i);
			if (Integer.parseInt(x) < 256 && (x.equals("0") || !(x.charAt(0) == '0'))) {
				res.add(x);
				dfs(str, index + i, level + 1, res);
				res.remove(( res.size()-1 ));
			}
		}
	}
```





#### 

 ### 左右翻转

这是一道华为面试原题（[226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)），题目大意是：

输入二叉树如下：

![输入](https://user-gold-cdn.xitu.io/2019/10/11/16db82e996cfb397?w=220&h=230&f=jpeg&s=3294)

反转后输出：

![输出](https://user-gold-cdn.xitu.io/2019/10/11/16db82e997d2f501?w=220&h=232&f=jpeg&s=3442)

> 乍一看很难办，其实想一个解决方案很简单，这里我直接举三个方案：

##### 方法一：比如我们用递归的思路，本质思想是：★

1. 本质思想也是左右节点进行交换

2. 交换前递归调用对根结点的左右节点分别进行处理

3. 保证交换前左右节点已经翻转。

三步搞定，我们看下代码实现：

```java
	   public TreeNode invertTree(TreeNode root) {	        
	        if (root == null) {
	            return null;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.push(root);	        
	        while(!stack.isEmpty()) {
	            final TreeNode node = stack.pop();
	            final TreeNode left = node.left;
	            node.left = node.right;
	            node.right = left;           
	            if(node.left != null) {
	                stack.push(node.left);
	            }
	            if(node.right != null) {
	                stack.push(node.right);
	            }
	        }
	        return root;
	    }
```

##### 方法二：循环，队列存储（BFS，非递归）★

本质思想是：

1. 左右节点进行交换

2. 循环翻转每个节点的左右子节点

3. 将未翻转的子节点存入队列中

4. 循环直到栈里所有节点都循环交换完为止。

```java
	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			TreeNode left = node.left;
			node.left = node.right;
			node.right = left;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return root;
	}
```

##### 方法三：「压轴出场，三步秒杀」递归 ★★

本质思想是：

1. 左右节点进行交换

2. 交换前递归调用对根结点的左右节点分别进行处理

3. 保证交换前左右节点已经翻转。

同样三步搞定，我们看下代码：

```java
public void invert(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invert(root.left);
    invert(root.right);
}
```

<br>
<br>

----



#### 

### [重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)

- 题目

- 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

- 具体数据如下：

  ```xml
  前序：A B D E H I C F G
  中序：D B H E I A F C G
  ```

- 思路

- 在上面的前序序列中，我们可以很容易地获得A就是根节点。此时，我们可以在后序序列中找到这个A，那么在A的左边就是A的左孩子及其子节点，在A的右边就是A的右孩子及其子节点。
- 假设，我们目前在A的左边。在遍历前序序列到B的时候，我就知道了B就是A的左孩子，而在B的左边(中序序列)的都是B的左孩子及其子节点，在B的右边(同是也在A的左边)的就是B的右孩子及其子节点...以此类推.这就是利用递归来重建二叉树。

- 代码

```java
class Solution {
    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] po;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++) 
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1);
        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}
```



#### 

### 最大值 ★

乍一看，是到送分题。我第一眼的想法就是：在方法中定义max用来保存遍历得到的最大值，结果每次递归时，都等于在重新定义max，这种方法不对。所以怎么办？

1. 采用分治思想

2. 从整棵树的底部开始

3. 两两比较，放回最大值

看一眼算法你就懂了

```java
public int getMax(TreeNode root) {
    if (root == null) {
        return Integer.MIN_VALUE;
    } else {
        int left = getMax(root.left);
        int right = getMax(root.right);
        return Math.max(Math.max(left, rigth), root.val);
    }
}
```

<br>
<br>

-----

#### 

### 最大深度 ★

深度问题和最大值一样，容易想复杂，其实非常简单，也可以看作一种分治的思想

1. 二叉树的最大深度是距根节点路径最长的某一树叶节点的深度。

2. 二叉树的深度等于二叉树的高度，也就等于根节点的高度。根节点的高度为左右子树的高度较大者+1。

- 视频

[【算法面试题】求二叉树最大的深度](https://www.bilibili.com/video/av46362459?from=search&seid=6708340101062499578)

```java
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}
```

<br>
<br>

----

#### 

### 最小深度

这道题目太常见了，当我一看到题目时就错了：

> 题目：最小深度是从根节点到最近`叶子节点`的最短路径上的节点数量。
> 说明: 叶子节点是指没有子节点的节点。

看到了吧，这时就得明确正确的递归结束条件

- 举个例子:
很多人写出的代码都不符合 1,2 这个测试用例，是因为没搞清楚题意

**题目中说明:** 叶子节点是指没有子节点的节点，这句话的意思是 1 不是叶子节点

题目问的是到叶子节点的最短距离，所以所有返回结果为 1 当然不是这个结果

另外这道题的关键是搞清楚递归结束条件

- 叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
- 当 root 节点左右孩子都为空时，返回 1
- 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
- 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值

- 视频

[二叉树的最小深度](https://www.bilibili.com/video/av46402848?from=search&seid=11873133572920668284)

```java
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    
    if (left == 0) {
        return right + 1;
    } else if (right == 0) {
        return left + 1;
    } else {
        return Math.min(left, right) + 1;
    }
}
```

<br>
<br>

----

#### 

### 平衡二叉树

概念：平衡二叉树每一个节点的左右两个子树的高度差不超过 1

1. 设一个 flag

2. 如果发现不平衡则就返回非 flag

- 视频

[平衡二叉树](https://www.bilibili.com/video/av46401915?from=search&seid=207860370482524655)

```java
public boolean isBalanced(TreeNode root) {
    return maxDepth(root) != -1;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}
```


<br>
<br>

----