47道 LeetCode 题解带你搞懂二叉树（一）
这两天休假回家，本周就不再更新其他内容了，提前祝大家周末愉快！
本文为LeetCode题解二叉树的第一篇，主要包括二叉树的基本概念和操作，以及LeetCode二叉树遍历、二叉树公共祖先问题题解。
对于树这个结构，最常见的就是二叉树。我们除了需要了解二叉树的基本操作之外，还需要了解一些特殊的二叉树，比如二叉搜索树、平衡二叉树等，另外还要熟悉二叉树的遍历方式，比如前序遍历、中序遍历、后序遍历、层序遍历。另外还要知道二叉树的常用遍历的方式：深度优先遍历和广度优先遍历。
一、二叉树的概念
关于“树”，有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：
节点的高度：节点到叶子节点的最长路径（边数） 节点的深度：根节点到这个节点所经历的边的个数 节点的层数：节点的深度 +1 树的高度：根节点的高度
1. 什么是二叉树？
二叉树（binary tree）是一种特殊的树，它是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
二叉树具有以下特点：
每个结点最多有两颗子树，结点的度最大为2（一个节点含有的子树的个数称为该节点的度）。 左子树和右子树是有顺序的，顺序不能颠倒。 即使某结点只有一个子树，也要区分左右子树。
存储二叉树有两种方法，
基于指针或者引用的二叉链式存储法， 基于数组的顺序存储法。
（1）链式存储法
从下图可以看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用。大部分二叉树代码都是通过这种结构来实现的。
（2）顺序存储法
把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
不过，上面是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。看下面这个例子：
所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
2. 满二叉树
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡。
根据满二叉树的定义，得到其特点为：
叶子只能出现在最下一层。 非叶子结点度一定是2。 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。
3. 完全二叉树
对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。其中关键点是按层序编号，然后对应查找。下图就是一个完全二叉树：
结合完全二叉树定义得到其特点：
叶子结点只能出现在最下一层（满二叉树继承而来） 最下层叶子结点一定集中在左 部连续位置。 倒数第二层，如有叶子节点，一定出现在右部连续位置。 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。
完全二叉树的性质：
具有 n 个结点的完全二叉树的深度为 K =「log2n」+1(取下整数) 有 n 个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若 i 为结点编号（从1开始编号）则 如果 i>1，则其父结点的编号为 i/2； 完全二叉树，如果 2 * i <= n，则其左儿子（即左子树的根结点）的编号为2 * i；若2 * i > n，则无左儿子；如果 2 * i + 1 <= n，则其右儿子的结点编号为 2 * i + 1；若 2 * i + 1 > n，则无右儿子。
4. 二叉查找树
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。
二叉查找树的根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值， 这一规则适用于二叉查找树中的每一个节点。下图就是二叉查找树：
二叉排序树要么是空二叉树，要么具有如下特点：
如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值； 如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值； 左右子树也要求都是二叉排序树； 在二叉查找树中，会尽可能规避两个结点数值相等的情况； 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。
在利用二叉查找树执行查找操作时，可以进行以下判断：
首先判断根结点是否等于要查找的数据，如果是就返回。 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。 这样的“二分查找”所消耗的时间复杂度就可以降低为 O(logn)。
5. 平衡二叉查找树（AVL）
平衡二叉查找树具有如下几个性质：
可以是空树。 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1。
上图就是一棵平衡二叉树。
平衡二叉树是为了解决二叉查找树中出现链式结构（只有左子树或只有右子树）的情况，这样的情况出现后对我们的查找没有一点帮助，反而增加了维护的成本。
平衡因子使用两个字母来表示。第一个字母表示最小不平衡子树根结点的平衡因子，第二个字母表示最小不平衡子树较高子树的根结点的平衡因子。根据不同的情况使用不同的方法来调整失衡的子树。
二、二叉树的操作
对于二叉树这个数据结构，只有解决了遍历问题，才能通过树来进行数据的增删查操作。所谓的二叉树遍历指的是：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。
常见的二叉树遍历方式有前序遍历、中序遍历、后序遍历和层序遍历，每种遍历方法都可以用递归和迭代的方式来实现，这里的序指的是父结点的遍历顺序，前序就是先遍历父结点，中序就是中间遍历父结点，后序就是最后遍历父结点。其中前序遍历、中序遍历、后序遍历是基于深度优先遍历的，层序遍历是基于广度优先遍历的。
上图中二叉树的结构及其编码：
const root = {
val: "A",
left: {
val: "B",
left: {
val: "D"
},
right: {
val: "E"
}
},
right: {
val: "C",
left: {
val: "F"
},
right: {
val: "G"
}
}
};
1. 前序遍历
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树，即根—左—右。
遍历结果：A -> B -> D -> E -> C -> F -> G
（1）递归实现
function preorder(root){
if(!root){
return
}
console.log(root.val) // 打印当前遍历的节点
preorder(root.left) // 递归遍历左子树
preorder(root.right) // 递归遍历右子树
}
（2）非递归实现
初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）若top的右子节点不为空，将top的右子节点放入栈中
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）将取出的栈顶元素top放入结果数组
function preorder(root){
if(!root){
return [];
}
var result = []
var stack = [root]
while(stack.length){
var top = stack.pop();
if(top.right){
stack.push(top.right);
}
if(top.left){
stack.push(top.left);
}
result.push(top.val);
}
return result;
}
2. 中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树，即左—根—右。
遍历结果：D -> B -> E -> A -> F -> C -> G
（1）递归实现
function inorder(root) {
if(!root) {
return
}
inorder(root.left) // 递归遍历左子树
console.log(root.val) // 打印当前遍历的结点
inorder(root.right) // 递归遍历右子树
}
（2）非递归实现
初始化一个栈和结果数组，当栈不为空时，重复下面的步骤：
（1）将根节点和所有的左子节点放入栈中，直到没有左子节点
（2）栈顶元素出栈，存入结果数组，将出栈的元素作为根节点
（3）查看该根节点右子节点是否有左子节点，若有就入栈，否则继续出栈
function inorder(root) {
if(!root){
return [];
}
var result = []
var stack = []
while(stack.length || root){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.push(root.val)
root = root.right;
}
return result;
}
（3）后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点，即左—右—根。
遍历结果：D -> E -> B -> F -> G -> C -> A
（1）递归实现
function postorder(root) {
if(!root) {
return
}
inorder(root.left) // 递归遍历左子树
inorder(root.right) // 递归遍历右子树
console.log(root.val) // 打印当前遍历的结点
}
（2）非递归实现
初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）将取出的栈顶元素top放入结果数组的最开始
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）若top的右子节点不为空，将top的右子节点放入栈中
function postorder(root) {
if(!root){
return [];
}
var result = []
var stack = [root]
while(stack.length){
var top = stack.pop();
result.unshift(top.val);
if(top.left){
stack.push(top.left);
}
if(top.right){
stack.push(top.right);
}
}
return result;
}
4. 层序遍历
基本思想： 层序遍历就是从上到下，从左到右打印二叉树的节点。
遍历结果：A -> B -> C -> D -> E -> F -> G
创建一个数组存放结果，一个队列存放二叉树的节点，如果存放二叉树的队列不为空，就重复下面的步骤：
（1）将队列的第一个节点作为根节点，并放入结果数组中
（2）如果该根节点的左子树不为空，就将其放入队列中
（3）如果该根节点的右子树不为空，就将其放入队列中
基本实现：
function levelTraversal(root){
if(!root){
return [];
}
var queue = [root];
var result = [];
while (tree.length){
var node = queue.shift();
result.push(node.val);
if(node.left){
queue.push(node.left);
}
if(node.right){
queue.push(node.right);
}
}
return result;
}
5. 总结
可以看到，二叉树遍历过程中，每个结点都被访问了一次，其时间复杂度是 O(n)。接着，在找到位置后，执行增加和删除数据的操作时，只需要通过指针建立连接关系就可以了。对于没有任何特殊性质的二叉树而言，抛开遍历的时间复杂度以外，真正执行增加和删除操作的时间复杂度是 O(1)。树数据的查找操作和链表一样，都需要遍历每一个数据去判断，所以时间复杂度是 O(n)。
三、LeetCode 二叉树的遍历
1. 二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
迭代实现： 初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）若top的右子节点不为空，将top的右子节点放入栈中
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）将取出的栈顶元素top放入结果数组
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 迭代的写法：
var preorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var stack = [root]
while(stack.length!==0){
var top = stack.pop();
if(top.right){
stack.push(top.right);
}
if(top.left){
stack.push(top.left);
}
result.push(top.val);
}
return result;
};
// 递归的写法：
var preorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var preorderTraversalNode = (node) => {
if(node) {
result.push(node.val)
preorderTraversalNode(node.left)
preorderTraversalNode(node.right)
}
}
preorderTraversalNode(root)
return result
};
迭代的复杂度：
时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。
递归的复杂度：
时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。
2. 二叉树的中序遍历
给定一个二叉树，返回它的 中序 遍历。示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
迭代实现： 初始化一个栈和结果数组，当栈不为空时，重复下面的步骤：
（1）将根节点和所有的左子节点放入栈中，直到没有左子节点
（2）栈顶元素出栈，存入结果数组，将出栈的元素作为根节点
（3）查看该根节点右子节点是否有左子节点，若有就入栈，否则继续出栈
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 迭代的实现：
var inorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var stack = []
while(stack.length!==0||root){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.push(root.val)
root = root.right;
}
return result;
};
// 递归的实现
var inorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var inorderTraversalNode = (node) => {
if(node) {
inorderTraversalNode(node.left)
result.push(node.val)
inorderTraversalNode(node.right)
}
}
inorderTraversalNode(root)
return result
};
迭代的复杂度：
时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。
递归的复杂度：
时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。
3. 二叉树的后序遍历
给定一个二叉树，返回它的后序遍历。示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
迭代实现： 二叉树的后序遍历和前序遍历是一个相反的过程，所以基本思路和前序遍历类似。初始化一个栈和结果数组，将根节点放入栈中，当栈不为空时，重复下面的步骤：
（1）取出栈顶元素top，访问top
（2）将取出的栈顶元素top放入结果数组的最开始
（3）若top的左子节点不为空，将top的左子节点放入栈中
（4）若top的右子节点不为空，将top的右子节点放入栈中
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 迭代的实现：
var postorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var stack = [root]
while(stack.length!==0){
var top = stack.pop();
result.unshift(top.val);
if(top.left){
stack.push(top.left);
}
if(top.right){
stack.push(top.right);
}
}
return result;
};
// 递归的实现
var postorderTraversal = function(root) {
if(!root){
return [];
}
var result = []
var postorderTraversalNode = (node) => {
if(node) {
postorderTraversalNode(node.left)
result.push(node.val)
postorderTraversalNode(node.right)
}
}
postorderTraversalNode(root)
return result
};
迭代的复杂度：
时间复杂度，每个结点都入栈出栈一次，遍历整棵树的时间复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度就是栈的最大使用空间，而这个空间是由树的高度决定的，所以空间复杂度就是 O(H)，H 表示二叉树的高度。
递归的复杂度：
时间复杂度，树上的每个结点都只访问一次，并且每次访问都只有一次压栈弹栈操作，所以复杂度为 O(N)，N表示二叉树的节点数。 空间复杂度，由于函数调用栈的深度与树的高度有关系，所以使用的空间为 O(H)。H 表示二叉树的高度。
4. 二叉树的层序遍历
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
创建一个数组存放结果，一个队列存放二叉树的节点，根据输出的要求，设置一个level，储存当前层数，如果存放二叉树的队列不为空，就重复下面的步骤：
（1）将队列的第一个节点作为根节点，并放入当前层的结果数组中
（2）如果该根节点的左子树不为空，就将其放入队列中
（3）如果该根节点的右子树不为空，就将其放入队列中
（4）遍历完该层之后，就遍历下一层
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root){
return [];
}
var queue = [root];
var result = [];
var level = 0;
while (queue.length!==0){
result[level]=[];
var levelNum = queue.length;
while(levelNum--){
var node = queue.shift();
result[level].push(node.val);
if(node.left){
queue.push(node.left);
}
if(node.right){
queue.push(node.right);
}
}
level++;
}
return result;
};
复杂度分析：
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)，其中n是二叉树的节点数。 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)，其中n是二叉树的节点数。
5. 二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。例如：给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
对于这道题目，对二叉树进行层序遍历，最直接的方法就是使用BFS（广度优先遍历）。
首先创建一个队列，将当前节点放进去，队列中的节点始终是当前层的节点。按顺序出列，加入结果中，并将当前节点的子节点加入到队列中。重复上述步骤，直到队列为空，就遍历完了整个二叉树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
if(!root) {
return []
}
const queue = []
queue.push(root)
const res = [] // 用来储存最后的结果
while(queue.length){
const subRes = [] // 用来储存每一层的节点值
const levelSize = queue.length
for(let i = 0; i < levelSize; i++){
const cur = queue.shift()
subRes.push(cur.val)
if(cur.left){
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
res.unshift(subRes)
}
return res
};
复杂度分析：
时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点访问一次，结果列表使用链表的结构时，在结果列表头部添加一层节点值的列表的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。 空间复杂度：O(n)，其中 n 是二叉树中的节点数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
6. 二叉树的锯齿形层序遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
可以采用递归的方式来解答，每一层都创建一个数组，奇数层从左往右依次插入数组，偶数层从右往左依次插入数组。
思路不是很难，这里我们使用i & 1来判断层数的奇偶：
i & 1 == 1 // 奇数
i & 1 == 0 // 偶数
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function(root) {
const res = []
function dfs(i, current){
if(!current) return
if(!Array.isArray(res[i])){
res[i] = []
}
if(i & 1){
res[i].unshift(current.val)
}else{
res[i].push(current.val)
}
dfs(i + 1, current.left)
dfs(i + 1, current.right)
}
dfs(0, root)
return res
};
复杂度分析：
时间复杂度：O(n)，其中 n 为二叉树的节点数。每个节点会且仅会被遍历一次，时间复杂度为 O(n)。 空间复杂度：O(n)，其中 n 为二叉树的节点数。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(n)。
五、LeetCode公共祖先问题
1. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
对于二叉树的题目，经常用的就是递归遍历，这里我们也使用到了递归：
首先判断，如果树为空树或p、q中任意一节和根节点相等，那么p和q 的最近公共祖先节点就是根节点root。
如果树不为空树，并且p和q和根节点不相等，那么就递归遍历左右子树：
如果p和q节点在左右子树的最近公共祖先节点都存在，说明p和q分布在左右子树上，则它们的最近公共祖先节点就是根节点root。 如果只有一个子树递归有结果，说明p和q都在这个子树中，那么就返回该树的递归的结果。 如果两个子树递归结果都为null，说明p和q都不在这俩子树中，那么就返回根节点root。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(!root || root === p || root === q){
return root
}
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
if(!left) return right
if(!right) return left
return root
};
复杂度分析：
时间复杂度: O(n)，其中 n 是二叉树节点的个数。这里遍历了二叉树的每个节点，所以时间复杂度为O(n)。 空间复杂度: O(n)，其中 n 是二叉树节点的个数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 n，所以空间复杂度为 O(n)。
2. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。
对于这道题目，我们可以使用递归或者迭代来实现。
（1）递归实现： 对于二叉树搜索树：
如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树； 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树； 如果 p.val 和 q.val 一个比 root.val 大，一个比 root.val 小，那说明这两个节点的最进公共祖先就是root；**
（2）迭代实现： 我们可以使用一个 while 循环，当 root 为 null 时就结束循环：
如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树，root=root.left，遍历到 root 的左子节点。 如果 p.val 和 q.val 都比 root.val 大，则 p、q 肯定在 root 的右子树，root=root.right，遍历到 root 的右子节点。 其他情况，当前的 root 就是最近公共祖先，结束遍历，直接结束循环。
递归实现：
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
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
};
迭代实现：
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
while(root){
if(p.val < root.val && q.val < root.val){
root = root.left
}else if(p.val > root.val && q.val > root.val){
root = root.right
}else{
break
}
}
return root
};
迭代复杂度分析：
时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况下，我们需要深度优先遍历整棵二叉树； 空间复杂度：O(1)，我们只需要常量空间来操作。
递归复杂度分析：
时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。最坏的情况选，我们需要深度优先遍历整棵二叉树； 空间复杂度：O(n)，我们需要递归遍历这棵树，所以空间复杂度为O(n)；