二叉树总结

树的遍历

不管是什么题目，树的遍历就是核心，这是一切的基础

递归遍历（DFS）

先来看看二叉树的递归前序遍历代码：

var preorderTraversal = function(root) {
    var list = []
    inOrder(root, list)
    return list
};

function inOrder (root, list) {
    if (!root) {
        return
    }
    list.push(root.val)
    inOrder(root.left, list)
    inOrder(root.right, list)
}

前中后续遍历的区别就在于 list.push(root.val) 的位置放在哪

前序遍历：

function dfs(root) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
    }
    // 主要逻辑
    dfs(root.left)
    dfs(root.right)
}

中序遍历：

function dfs(root) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
    }
    dfs(root.left)
	// 主要逻辑
    dfs(root.right)
}

后序遍历：

function dfs(root) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
    }
    dfs(root.left)
    dfs(root.right)
	// 主要逻辑
}

N叉树的遍历：

function dfs(root) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
	}
	for (const child of root.children) {
		dfs(child)
	}
}

迭代遍历（BFS）

先来看看二叉树的迭代前序遍历代码:

var preorderTraversal = function(root) {
    if (root === null) {
        return []
    }
    let list = []
    let queue = []
    while (queue.length || root !== null) {
        while (root !== null) {
            list.push(root.val);
            queue.push(root);
            root = root.left;
        }
        root = queue.pop();
        root = root.right;
    }
    return list
};

迭代法的前中后续遍历区别就在于根据规则调整左右子节点的入栈顺序

中序遍历:

var inorderTraversal = function(root) {
    if (root === null) {
        return []
    }
    const list = [];
    const queue = [];
    while (root || queue.length) {
        while (root) {
            queue.push(root);
            root = root.left;
        }
        root = queue.pop();
        list.push(root.val);
        root = root.right;
    }
    return list;
};

后续遍历有点特别：

var postorderTraversal = function(root) {
    if (root === null) {
        return []
    }
    const list = [];
    const queue = [];
    let prev = null
    while (root || queue.length) {
        while (root) {
            queue.push(root);
            root = root.left;
        }
        root = queue.pop();
        if (root.right === null || root.right === prev) {
            list.push(root.val);
            prev = root;
            root = null;
        } else {
            queue.push(root);
            root = root.right;
        }
    }
    return list;
};

N叉树的遍历：

var preorder = function(root) {
    if (root === null) {
        return []
    }
    let array = []
    let stack = [root]
    while (stack.length) {
        let len = stack.length
        let node = stack.shift() // 弹出栈中第一个，先进先出
        array.push(node.val)
        if (node.children.length > 0) {
            stack = node.children.concat(stack) // 这里有别于层序遍历，用 node.children 连接 queue，而不是 queue.concat(node.children)这样就实现了前序遍历的效果
        }
    }
    return array
};

层序遍历

BFS不是层序遍历，层序遍历就是一层层遍历树，按照树的层次顺序进行访问。

二叉树的层序遍历

var levelOrder = function(root) {
    var list = []
    if (!root) {
        return list
    } else {
        let queue = [root]
        while(queue.length) {
            let len = queue.length
            let array = []
            while (len) {
                let nowRoot = queue.shift()
                array.push(nowRoot.val)
                if (nowRoot.left) {
                    queue.push(nowRoot.left)
                }
                if (nowRoot.right) {
                    queue.push(nowRoot.right)
                }
                len--
            }
            list.push(array)
        }
    }
    return list
};

N 叉树的层序遍历

var levelOrder = function(root) {
    if (root === null) {
        return []
    }
    let queue = [ root ]
    let resultArray = []
    while (queue.length) {
        let len = queue.length
        let array = []
        while (len) {
            let node = queue.shift()
            array.push(node.val)
            for (i = 0; i < node.children.length; i++) {
                if (node.children[i] !== null) {
                    queue.push(node.children[i])
                }
            }
            len--
        }
        resultArray.push(array)
    }
    return resultArray
};

三种题型

树的题目就三种类型，分别是：搜索类，构建类和修改类，而这三类题型的比例也是逐渐降低的。

搜索类

搜索类只有两种解法，那就是 DFS 和 BFS，所有搜索类的题目只要把握三个核心点，即开始点，结束点和目标即可。

构建类

二叉树的构建分为4种：

给你两种 DFS 的遍历的结果数组，让你构建出原始的树结构。比如根据先序遍历和后序遍历的数组，构造原始二叉树。
给你一个 BFS 的遍历的结果数组，让你构建出原始的树结构。
还有一种是给你描述一种场景，让你构造一个符合条件的二叉树。
二叉搜索树的构建。

修改类

一种是题目让你增加，删除节点，或者是修改节点的值或者指向
另外一种是为了方便计算，自己加了一个指针

关于二叉搜索树：

二叉搜索树中序遍历序列的下一个节点。即比当前节点大的最小节点，简称后继节点。先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。

二叉搜索树中序遍历序列的前一个节点。即比当前节点小的最大节点，简称前驱节点。先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点。

注意：需要返回增删改后的节点时，一般利用当前函数递归，不需要创建新的递归函数，并且返回节点。

重要概念

二叉搜索树

二叉搜索树（Binary Search Tree），亦称二叉查找树。

二叉搜索树具有下列性质的二叉树：

若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
左、右子树也分别为二叉排序树；
没有键值相等的节点。

对于一个二叉查找树，常规操作有插入，查找，删除，找父节点，求最大值，求最小值。

二叉搜索树的中序遍历是有序的，天生适合查找。

完全二叉树

一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

我们可以给完全二叉树编号，这样父子之间就可以通过编号轻松求出。比如我给所有节点从左到右从上到下依次从 1 开始编号。那么已知一个节点的编号是 i，那么其左子节点就是 2 _ i，右子节点就是 2 _ 1 + 1，父节点就是 (i + 1) / 2。

熟悉二叉堆的同学可能发现了，这就是用数组实现的二叉堆，其实二叉堆就是完全二叉树的一个应用。

路径

树的路径这种题目的变种很多，算是一种经典的考点了。

要明白路径的概念，以及如何解决这种题，只需要看一个题目就好了 124.二叉树中的最大路径和

距离

和路径类似，距离也是一个相似且频繁出现的一个考点，并且二者都是搜索类题目的考点。原因就在于最短路径就是距离，而树的最短路径就是边的数目。

这两个题比较有代表性:

863. 二叉树中所有距离为 K 的结点

834. 树中距离之和

解题技巧

单/双递归

树的题目大多数都可以用递归轻松地解决。如果一个递归不行，那么来两个。

双递归的基本套路就是一个主递归函数和一个内部递归函数。主递归函数负责计算以某一个节点开始的 xxxx，内部递归函数负责计算 xxxx，这样就实现了以所有节点开始的 xxxx。但是如果递归中有重复计算，则可以使用双递归 + 记忆化或者直接单递归。

前后遍历

如果是前序遍历，那么你可以想象上面的节点都处理好了，怎么处理的不用管。相应地如果是后序遍历，那么你可以想象下面的树都处理好了，怎么处理的不用管。

总结下我的经验：

大多数树的题使用后序遍历比较简单，并且大多需要依赖左右子树的返回值。
不多的问题需要前序遍历，而前序遍历通常要结合参数扩展技巧。
如果你能使用参数和节点本身的值来决定什么应该是传递给它子节点的参数，那就用前序遍历。
如果对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出当前节点的答案，那就用后序遍历。
如果遇到二叉搜索树则考虑中序遍历

虚拟节点

不仅仅链表有虚拟节点的技巧，树也是一样。关于这点大家可能比较容易忽视。

我们通常在什么时候才会使用？

链表的头会被修改。这个时候通常需要一个虚拟指针来做新的头指针，这样就不需要考虑第一个指针的问题了（因为此时第一个指针变成了我们的虚拟指针，而虚拟指针是不用参与题目运算的）。树也是一样，当你需要对树的头节点（在树中我们称之为根节点）进行修改的时候，就可以考虑使用虚拟指针的技巧了。
另外一种是题目需要返回树中间的某个节点（不是返回根节点）。实际上也可借助虚拟节点。由于我上面提到的指针的操作，实际上，你可以新建一个虚拟头，然后让虚拟头在恰当的时候（刚好指向需要返回的节点）断开连接，这样我们就可以返回虚拟头的 next 就 ok 了。

参数扩展大法

参数扩展这个技巧非常好用，一旦掌握你会爱不释手。

有时候，我们需要 dfs 携带更多的有用信息。典型的有以下三种情况：

携带父亲或者爷爷的信息
携带路径信息，可以是路径和或者具体的路径数组等。
二叉搜索树的搜索题大多数都需要扩展参考，甚至怎么扩展都是固定的。