二叉树理论基础

?Java 与 C++ 对应的数据结构

来源：https://blog.csdn.net/wangcfbj/article/details/70269995

对应数据结构实现的原理

Java中TreeMap、TreeSet的底层实现都是平衡二叉搜索树
所以TreeMap、TreeSet的增删操作时间时间复杂度是logn，
而HashMap、HashSet底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针，顺序存储的方式就是用数组。
如图：

顺序存储就是用数组来存储二叉树，顺序存储的方式如图：

用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
所以大家要了解，用数组依然可以表示二叉树。

二叉树的遍历方式

关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。
这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。
二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
广度优先遍历
- 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历，这里前中后**，其实指的就是中间节点的遍历时的位置**，只要大家记住前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

例如，以下是前中后序遍历结果：

最后再说一说二叉树中深度优先和广度优先遍历实现方式
我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
另外，之前在栈与队列的时候，栈其实就是递归的一种实现结构
也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现后面都会详细讲，这里大家先要清楚这些理论基础。

二叉树的定义

我们来看看链式存储的二叉树节点的定义方式。

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;
    }
}

要注意二叉树节点定义的书写方式❗❗❗
在现场面试的时候面试官可能要求手写代码，所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。
因为我们在刷leetcode的时候，节点的定义默认都定义好了，真到面试的时候，需要自己写节点定义的时候，有时候会一脸懵逼！

总结

二叉树是一种基础数据结构，在算法面试中都是常客，也是众多数据结构的基石。
本篇我们介绍了二叉树的存储方式、遍历方式以及定义，比较全面的介绍了二叉树各个方面的重点，帮助大家扫一遍基础。
说到二叉树，就不得不说递归，很多同学对递归都是又熟悉又陌生，递归的代码一般很简短，但每次都是一看就会，一写就废。

二叉树的递归遍历

为什么很多同学看递归算法都是“一看就会，一写就废”。
主要是对递归不成体系，没有方法论，每次写递归算法，都是靠玄学来写代码，代码能不能编过都靠运气。
本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，**我们要通过简单题目把方法论确定下来，**有了方法论，后面才能应付复杂的递归。
这里确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

确定递归函数的参数和返回值： 哪些参数需要处理？需不需要返回值，返回值是什么？确定参数和返回类型
确定终止条件： 递归如同for，while循环，需要一个终止条件。递归时经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以下以前序遍历为例：

确定递归函数的参数和返回值：参数：由于ArrayList来放节点的数值，因此参数中有Arraylist，同时需要确定开始遍历的节点有TreeNode。有了Arraylist存储，方法不需要返回参数，所以递归函数返回类型就是void，代码如下：

public void preorder(TreeNode root, List<Integer> result) {}

确定终止条件：当递归结束时，当前遍历的节点为空，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (root == null) {
            return;
        }

确定单层递归的逻辑：想象只有一次递归，前序遍历是中左右的循序，所以在单层递归的逻辑中，是要先取中节点的数值，代码如下：

result.add(root.val);			// 中
preorder(root.left, result);	// 左
preorder(root.right, result);	// 右

因此完整代码如下:

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }


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

}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

二叉树的迭代遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
我们在1047. 删除字符串中的所有相邻重复项 (神似消消乐的算法)中提到了，
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
递归底层是迭代，而实现迭代的数据结构是栈。因此，栈也可以实现二叉树的前中后序遍历

前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。
动画如下：
图片[3]-羊羊刷题笔记Day13/60 | 第六章二叉树P1 | 二叉树理论基础、递归遍历、迭代遍历与总结-五八三
不难写出如下代码: （注意代码中空节点不入栈）

public List<Integer> preorderTraversal(TreeNode root) {
    // 方法2:使用栈实现迭代 - 前序遍历:中左右
    // 初始化变量
    Stack<TreeNode> s = new Stack<>();
	ArrayList<Integer> list = new ArrayList<>();
	if (root == null) return list;


	// 先把根节点放入
	s.push(root);
	// 循环判断(用栈模拟递归过程)
	while (!s.isEmpty()){
    	// 出栈取根节点 加入节点值并获取左右孩子.(注意入栈先右后左)
    	TreeNode node = s.pop();
    	list.add(node.val);
    	// 注意是if与if 不是if与if-else  因为左右节点都要判断
    	if (node.right != null) s.push(node.right);
    	if (node.left != null) {
        	s.push(node.left);
    	}
	}
	return list;
}

后序遍历（迭代法）

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。中左右 – 中右左 – 左右中
代码如下：

public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    Stack<TreeNode> s = new Stack<>();

    if (root == null) return list;
    // 预先先放一个
    s.push(root);


    // 用栈模拟递归
    while (!s.isEmpty()) {
        // 相比前序遍历,调换了左右顺序,变成中右左
        TreeNode node = s.pop();
        list.add(node.val);
        if (node.left != null) s.push(node.left);
        if (node.right != null) s.push(node.right);
    }

    // 翻转后得:左右中 - 后序遍历
    Collections.reverse(list);
    return list;
}

中序遍历（迭代法）

为了解释清楚，我说明一下刚刚在迭代的过程中，其实我们有两个操作：

处理：将元素放进result数组中
访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：
中序遍历，可以写出如下代码：

public List<Integer> inorderTraversal(TreeNode root) {
    // 方法2：用栈实现迭代模拟递归
    ArrayList<Integer> list = new ArrayList<>();
    if (root == null){
        return list;
    }


    Stack<TreeNode> s = new Stack<>();
    TreeNode cur = root;

    // 循环结束条件：遍历到最后,cur已经到最后(cur == null) 且 栈里没有元素弹出(s.isEmpty)
    while (cur != null || !s.isEmpty()){
        if (cur != null){
            // cur在往下探
            s.push(cur);
            cur = cur.left;
        }
        else {
            // cur探到尾节点的左右孩子(null) -> 找"父"节点(可能是爷爷节点)
            // 出栈,进list,探索右孩子
            cur = s.pop();
            list.add(cur.val);
            cur = cur.right;
        }
    }
    return list;
}