二叉树理论基础

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

对应数据结构完成的原理

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

二叉树的存储办法

二叉树能够链式存储，也能够次序存储。 那么链式存储办法就用指针， 次序存储的办法便是用数组。 如图：

次序存储便是用数组来存储二叉树，次序存储的办法如图：

二叉树的遍历办法

关于二叉树的遍历办法，要知道二叉树遍历的根本办法都有哪些。 这儿把二叉树的几种遍历办法列出来，咱们就能够一一串起来了。 二叉树主要有两种遍历办法：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
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的时分，节点的界说默许都界说好了，真到面试的时分，需求自己写节点界说的时分，有时分会一脸懵逼！

总结

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

二叉树的递归遍历

为什么许多同学看递归算法都是“一看就会，一写就废”。 主要是对递归不成体系，没有办法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。 本篇将介绍前后中序的递归写法，一些同学或许会感觉很简单，其实不然，**咱们要通过简单标题把办法论确认下来，**有了办法论，后边才能敷衍杂乱的递归。 这儿确认下来递归算法的三个要素。每次写递归，都按照这三要素来写，能够保证咱们写出正确的递归算法！

1. 确认递归函数的参数和回来值： 哪些参数需求处理？需不需求回来值，回来值是什么？确认参数和回来类型
2. 确认停止条件： 递归好像for，while循环，需求一个停止条件。递归时经常会遇到栈溢出的错误，便是没写停止条件或许停止条件写的不对。
3. 确认单层递归的逻辑： 确认每一层递归需求处理的信息。在这儿也就会重复调用自己来完成递归的进程。

以下以前序遍历为例：

1. 确认递归函数的参数和回来值：参数：由于ArrayList来放节点的数值，因而参数中有Arraylist，一起需求确认开端遍历的节点有TreeNode。有了Arraylist存储，办法不需求回来参数，所以递归函数回来类型便是void，代码如下：

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

2. 确认停止条件：当递归完毕时，当时遍历的节点为空，所以如果当时遍历的这个节点是空，就直接return，代码如下：

if (root == null) {
            return;
        }

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

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. 删去字符串中的一切相邻重复项 (神似消消乐的算法)中提到了， 递归的完成便是：每一次递归调用都会把函数的局部变量、参数值和回来地址等压入调用栈中，然后递归回来的时分，从栈顶弹出上一次递归的各项参数，所以这便是递归为什么能够回来上一层方位的原因。 递归底层是迭代，而完成迭代的数据结构是栈。因而，栈也能够完成二叉树的前中后序遍历

前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中心节点，那么先将根节点放入栈中，然后将右孩子参加栈，再参加左孩子。 为什么要先参加 右孩子，再参加左孩子呢？ 由于这样出栈的时分才是中左右的次序。 动画如下：

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

中序遍历（迭代法）

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

1. 处理：将元素放进result数组中
2. 拜访：遍历节点

剖析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，由于前序遍历的次序是中左右，先拜访的元素是中心节点，要处理的元素也是中心节点，所以刚刚才能写出相对简练的代码，由于要拜访的元素和要处理的元素次序是共同的，都是中心节点。 那么再看看中序遍历，中序遍历是左中右，先拜访的是二叉树顶部的节点，然后一层一层向下拜访，直到到达树左面的最底部，再开端处理节点（也便是在把节点的数值放进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;
}

总结

咱们用迭代法写出了二叉树的前后中序遍历，咱们能够看出前序和中序是彻底两种代码风格，并不像递归写法那样代码稍做调整，就能够完成前后中序。 原因是前序遍历中拜访节点（遍历节点）和处理节点（将元素放进result数组中）能够同步处理，可是中序就无法做到同步！

那么问题又来了，莫非 二叉树前后中序遍历的迭代法完成，就不能风格一致么（即前序遍历 改动代码次序就能够完成中序 和 后序）？——有，有爱好再学《一致迭代》

学习资料：

二叉树理论基础

递归遍历

迭代遍历

一致迭代（待学）