树

发表于 2015/02/23 更新于 2025/02/02

作者 Hacket Zeng

71 分钟阅读

树

二叉树基础

什么是二叉树？

二叉树（Binary Tree）是包含 n 个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树种类

完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

完全二叉树特点：

只允许最后一层有空缺节点且空缺节点在右边，即叶子节点只能在最后一层或次最后层出现
对任一节点，如果其右子树的深度为 j，则其左子树的深度必为 j 或 j+1

满二叉树

除最后一层无任何子节点外，每一层上的所有节点都有两个子节点二叉树

一颗二叉树，如果每一层的节点数都达到最大值，则这棵二叉树就是满二叉树。也就是说一颗二叉树的层数为 k，且节点总数为 2^k-1，则它就是满二叉树。

满二叉树特点：

一棵层数为 k 个满二叉树总节点数为 2^k-1，因此满二叉树的节点数一定是奇数个

如上面这棵树，层数为 3，其总节点为 2^3-1 = 7 个

第 i 层上的节点数为 2^(i-1)

第 1 层个数为 1，第 2 层个数为 2，第 3 层个数为 4

一个层数为 k 的满二叉树的叶子节点个数（最后一层）为 2^(k-1)

最后为第 3 层，其节点个数为 2^(3-1) = 4

二叉排序树

又称二叉查找树 (Binary Search Tree)，也称二叉搜索树，有以下性质：

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

平衡二叉树 AVL 树

平衡二叉树是二叉搜索树的进化版，左右两棵子树的高度差的绝对值不超过 1

红黑树

红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树；红黑树有一个重要的性质，从根节点到叶子节点的最长路径不多于最短路径的长度的两倍；对于红黑树，插入、删除、查找的时间复杂度都是 O(logN)

哈夫曼树

给定 n 个权值为 n 的叶子节点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman tree)

二叉树的遍历必须掌握

二叉树遍历介绍

二叉树遍历的四种方式

二叉树主要有四种遍历方式（xxx 序遍历，针对的是对根节点访问的时机）

先序遍历：即先访问根节点，再访问左孩子和右孩子 根左右；与 DFS（深度优先搜索）有一定联系
中序遍历：先访问左孩子，再访问根节点和右孩子 左根右；当二叉树为二叉搜索树时，中序遍历返回结果为有序序列
后序遍历：先访问左孩子，再访问右孩子和根节点 左右根
层序遍历：按照所在层数，从左到右，从下往上遍历；与 BFS（广度优先搜索）有一定联系

该二叉树对应的几种遍历方式的结果顺序：

先序遍历：10 6 1 8 14 12 16
中序遍历：1 6 8 10 12 14 16
后序遍历：1 8 6 12 16 14 10
层序遍历：10 6 14 1 8 12 16

二叉树遍历框架

递归法

  
void traversal(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traversal(root.left);
    // 中序位置
    traversal(root.right);
    // 后序位置
}

traversal() 是能够遍历二叉树所有节点的一个函数。

模板迭代法

  
public List<Integer> preorderTraversal3(TreeNode root) {
    // 边界
    if (root == null) return new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        // 先将所有左子节点加入到队列，并记录到res
        while (root != null) {
            // res.add(root.val);
            stack.push(root);
            root = root.left;
        }
        // 弹栈，切换到右子树，将其看成一颗新的树，重复上述操作
        TreeNode tmp = stack.pop(); // 可以直接复用root，方便理解定义新的变量tmp
        root = tmp.right;
    }
    return res;
}

二叉树前中后序遍历理解

前中后序位置

前序位置的代码在刚刚进入一个二叉树节点的时候执行；后序位置的代码在将要离开一个二叉树节点的时候执行；中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点
二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。

二叉树解题通用思路

是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要涉及到子树信息，建议使用后序遍历。

前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。
中序位置主要用在 BST(二叉搜索树)场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组
前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻；意味着前序位置的代码只能从函数参数中获取父节点传递过来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据

那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了

二叉树前序遍历 DFS

根→左→右

144. 二叉树的前序遍历

前序遍历 - 递归法

思路：

  
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    preorderTraversal(root, list);
    return list;
}
private void preorderTraversal(TreeNode root, List<Integer> list) {
    // 递归结束条件，子节点
    if (root == null) {
        return;
    }
    // 前序，先添加根
    list.add(root.val);
    // 访问左子节点
    preorderTraversal(root.left, list);
    // 访问右子节点
    preorderTraversal(root.right, list);
}

前序遍历 - 迭代法

思路 1：借助栈

初始化栈，并将根节点入栈；
当栈不为空时：
- 弹出栈顶元素 node，并将值添加到结果中；
- 如果 node 的右子树非空，将右子树入栈；（由于前序遍历是根左右，所以右子树先入栈，后弹出栈）
- 如果 node 的左子树非空，将左子树入栈；

  
public List<Integer> preorderTraversal2(TreeNode root) {
    // 边界
    if (root == null) return new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    // 借助栈
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val);
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return list;
}

思路 2：迭代模板 - 栈

它先将根节点 root 和所有的左孩子入栈并加入结果中，直到 root 为空（即所有左子树节点都入栈了），用一个 while 循环实现

然后，每弹出一个栈顶元素 tmp，就到达它的右孩子，再将这个节点作为一颗新的树重新按上面的步骤来一遍，直到栈为空，这也需要一个 while 循环

  
 public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        // 先将所有左子节点加入到队列，并记录到res
        while (root != null) {
            res.add(root.val);
            stack.push(root);
            root = root.left;
        }
        // 弹栈，切换到右子树，将其看成一颗新的树，重复上述操作
        TreeNode tmp = stack.pop(); // 可以直接复用root，方便理解定义新的变量tmp
        root = tmp.right;
    }
    return res;
}

思路 3：迭代模板 - 借助队列

前序遍历就是先遍历根；我们借助队列，不停的遍历树的左边，并将节点加入到队列头部，直到叶子节点，这个遍历过程中，将根节点加入到 res 中
当左子节点都加入完毕后，开始从队列头部一个个将元素取出来，并将该节点作为 root，可以认为是一颗新的树，重复上述操作
直到 root 为 null 或队列空了

  
public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    while (root != null || !queue.isEmpty()) {
        // 先序遍历，需要不停的先遍历
        while (root != null) {
            res.add(root.val);
            queue.offerFirst(root);
            root = root.left;
        }
        // 弹出
        root = queue.removeFirst();
        // 现在遍历右边
        root = root.right;
    }
    return res;
}

二叉树中序遍历

左→根→右
94. 叉树的中序遍历

中序遍历 - 递归法

  
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    inorderTraversal(root, res);
    return res;
}
private void inorderTraversal(TreeNode root, List<Integer> res) {
    // 递归结束条件：为叶子节点
    if (root == null) {
        return;
    }
    // 中序遍历：左根右
    inorderTraversal(root.left, res);
    res.add(root.val);
    inorderTraversal(root.right, res);
}

中序遍历 - 迭代法（借助栈）

尽可能的将这个节点的左子树压入 Stack，此时栈顶的元素是最左侧的元素，其目的是找到一个最小单位的子树 (也就是最左侧的一个节点)，并且在寻找的过程中记录了来源，才能返回上层,同时在返回上层的时候已经处理完毕左子树了。
当处理完最小单位的子树时，返回到上层处理了中间节点。（如果把整个左中右的遍历都理解成子树的话，就是处理完左子树 ->中间 (就是一个节点)->右子树）
如果有右节点，其也要进行中序遍历。当整个左子树退栈的时候这个时候输出了该子树的根节点 2，之后输出中间节点 1。然后处理根节点为 3 右子树。

  
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (root != null || !stack.isEmpty()) {
        // 左子树全部入栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // 所有左子树入栈，现在开始遍历右子树
        TreeNode tmp = stack.pop();
        // 每弹出一个节点，是左节点，将其加入到res
        res.add(tmp.val);
        // 遍历该节点的右子树，当成一颗新的树，重复上述操作；如果是叶子节点，其右子树为null
        root = tmp.right;
    }
    return res;
}

二叉树后序遍历

145.二叉树的后序遍历

后序遍历 - 递归法

  
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    postorderTraversal(root, res);
    return res;
}

private void postorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    postorderTraversal(root.left, res);
    postorderTraversal(root.right, res);
    res.add(root.val);
}

后序遍历 - 迭代 - 尾插法

思路：

后序遍历：左右根；那么我们反过来就是根右左
借助一个栈 Stack，和先序遍历类似，先序遍历是根左右，而我们这个不太一样都是先遍历根，再遍历右，最后遍历左节点
最后将结果给反转过来就好；也可以直接将元素头插 List（即插入在第 0 个位置）

  
public List<Integer> postorderTraversal(TreeNode root) {
    if (root==null) return new ArrayList<>();
    // 借助栈
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // 由于是倒序插入，从尾插到头，所以需要先遍历right，所以left先入栈
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
        // 倒序插入，根节点是最后一个
        res.add(0, node.val);
    }
    return res;
}

后续遍历 - 迭代解法（正序）

思路：

借助辅助栈 stack 存储临时访问的节点；借助 List 存储要输出的值
由于后序遍历是：左右根；所以需要将所有的左子节点都先加入到栈中
中序遍历是：左根右，而后序遍历不同，访问左子节点就完了吗？没有，还需要看下是否有右子节点，最后才访问根节点
每访问一个节点需要判断其是否有右子节点，有右子节点话，将该右子节点作为一颗新的子树，根为右子树，还需将出栈后的该节点重新入栈先处理其右子节点，重复 2 步骤
由于 4 步骤的节点可能存在右子节点，导致其父节点再次被入栈，那么当再次访问到该节点时，可能其右子节点已经处理完毕，所以我们还需要个临时节点 pre 记录该节点是右子节点已经访问了，如果访问了就不再加入到栈，否则会出现是循环
重复前步骤，直到栈为空且 root 为 null

  
public static List<Integer> postorderTraversal2(TreeNode root) {
    if (root == null) return new int[0];
    // 借助List存储遍历后要输出的节点
    List<Integer> list = new ArrayList<>();
    // 借助栈存储临时节点
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pre = null;
    while (!stack.isEmpty() || root != null) {
        // 先将所有的root的左节点加入到栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // 弹栈root的最左子节点
        TreeNode node = stack.pop();
        // 看看是否还有右子节点，且该右子节点没有被处理过
        if (node.right == null || node.right == pre) { // 没有右子节点，因为其父节点还会再次进入判断node.right是否为null，不为null的话会再次加入栈，导致了死循环，所以需要记录下已经处理过加入到list的节点，由于right节点是在其父节点前一个处理，所以用个pre就可以记录了
            // 没有右子节点，直接将该节点加入到List
            list.add(node.val);
            // 且记录为访问过了
            pre = node;
        } else { // 有右子节点
            // 如果有右子节点，那么将刚刚弹出的右子节点node再次入栈，先不处理，先处理其右子节点
            stack.push(node);
            // node.right成为新的根节点
            root = node.right;
        }
    }
    return list;
}

BFS: 二叉树层序遍历，不需按层输出

只需要将遍历结果存储到 keys 就行了，不需要临时的 List 来存储了

  
public Queue<Key> bfs() {
    // 定义两个队列，分别存储树中的键和树中的结点
    LinkedList<Key> keys = new LinkedList<>();
    LinkedList<Node<Key, Value>> nodes = new LinkedList<>();
    // 首先把根节点存到nodes中去
    nodes.offer(root);
    while (!nodes.isEmpty()) {
        // 将队列中第一个出队列
        Node<Key, Value> node = nodes.poll();
        // 存到keys中去
        keys.offer(node.key);
        // 看看是否有左子结点，有的话将结点加入nodes队列中
        if (node.left != null) {
            nodes.offer(node.left);
        }
        // 看看是否有右子结点，有的话将结点加入nodes队列中
        if (node.right != null) {
            nodes.offer(node.right);
        }
    }
    return keys;
}

BFS: 二叉树层序遍历，按层输出（medium）

题目：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

题解
BFS 遍历和层序遍历区别：
层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。
解决：在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点

1、队列迭代解法

思路：

辅助队列 queue 用来保存下一轮（下一层）需要遍历的节点；辅助 results 存储最终结果值
默认先将 root 添加到 queue 作为第一轮
遍历 queue，只要 queue 不为空
由于每次添加的是下一层所有的节点，所以内部再次循环遍历把这一层的节点都遍历出来（因为需要记录每层遍历的结果）
- 每遍历一个节点，将遍历结果临时添加到临时 temp
- 遍历一个节点结束后，将其 left 和 right 子节点添加 queue，作为下一轮的遍历（下一层）
- 遍历一层后将其添加到 results

不能用栈来辅助遍历，否则输出不对

  
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    // 判空
    if (root==null) return results;
    Queue<TreeNode> queue = new LinkedList<>();
    // 首先将root节点添加到queue
    queue.offer(root);
    // 总层数
    int level = 0;
    // 只要queue有元素，继续遍历
    while (!queue.isEmpty()) {
        // 当前层节点的数量
        int size = queue.size();
        // 存放当前层数层序遍历的节点
        List<Integer> temp = new ArrayList<>();
        // 遍历该层所有的节点
        for (int i = 0; i < size; i++) {
            // 一个个将该层的节点取出来
            TreeNode node = queue.poll();
            temp.add(node.val);

            // 将下一层的子节点添加到队列（left和right）
            TreeNode left = node.left;
            if (left != null) {
                queue.offer(left);
            }
            TreeNode right = node.right;
            if (right != null) {
                queue.offer(right);
            }
        }
        // 将当前层遍历的节点添加到list
        results.add(temp);
        level++;
    }
    System.out.println("level=" + level);
    return results;
}

2、递归解法

DFS 思路：
层序遍历要用递归的话，关键是找到这一层所有的节点，那么我们就定义一个 level 来表示当前这一层，每增加一层 level+1

res 存储所有层遍历的结果；list 存储指定层所有的遍历的节点；level 表示当前遍历到哪一层
利用树的层级 level 来定义每一层的节点，遍历到指定 level 层就新建一个 list 加入到 res，每层都有一个 List 存储该层的节点
- level 从 0 开始，因为有多少层，那么 res 的 size 就是 level+1，所以当遍历到 level=0 时，就需要新建一个 list 添加到 res；

第 0 层 list 有 1 个元素；第 1 层 list 有 2 个元素；第 level 层，那么 list 就有 level+1 个元素

每遍历一层 level，通过 level 获取存放当前层的 res，遍历该层的节点存放到 res 中去；

递归子问题：
- 遍历到当前节点，通过 level 从 res 中得到当前 level 的 list，然后将当前节点加入到 list
- 然后将当前节点的左/右孩子节点重复递归该操作
递归结束条件：当前节点为叶子节点

代码：

  
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
         List<List<Integer>> list = new ArrayList<>();
         if(root == null) return list;
         findLevelOrder(list, root, 0);
         return list;
    }
    public void findLevelOrder(List<List<Integer>> list,TreeNode currentNode,int level){
         if(currentNode==null) return;
         if(list.size()==level){
            List<Integer> subList=new ArrayList<>();
            list.add(subList);
         }
         list.get(level).add(currentNode.val);
         findLevelOrder(list,currentNode.left,level+1);
         findLevelOrder(list,currentNode.right,level+1);
    }
}

morris 遍历

什么是 morris 遍历？
morris 遍历是二叉树遍历算法的进阶算法，其他遍历算法均需要 O(n) 的时间复杂度，O(logn) 的空间复杂度；morris 遍历可以将非递归遍历中空间复杂度降为 O(1)，时间复杂度还是 O(n)。

中序 Morris 遍历

思路：

迭代遍历有栈来存储遍历过程中的父节点，而 Morris 只有一个临时变量 pre，用来在遍历过程中，保存寻找当前子树最右的子节点
开始遍历当前节点 root 的左子节点
1. 如果左子树为 null，代表没有左节点，直接将 root 添加到结果中；然后遍历 root 的右节点
2. 如果左子树不为 null，代表有左节点，在遍历左节点前，需要找到当前树右子树的最右孩子节点，让其后继节点指向自己
  - 找到了当前子树最右的子节点 pre 后，子节点的后继节点是 null，pre 的后继节点保存 root 节点，以解决后续遍历过程中回不到父节点的问题
  - 找到 pre 节点
    - pre 节点为空，说明是第一次访问 pre 节点，那么让 pre 的后继节点指向当前子树的根节点
    - pre 节点不为空，说明是最后访问了，需要恢复树的结构；过渡到下一个节点

代码：

  
public List<Integer> morrisInOrderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode pre;
    while (root != null) {
        if (root.left == null) { // 左子树为null，直接访问当前节点，然后访问右子树
            // 根据中序遍历：左根右，那么直接将当前节点加入
            res.add(root.val);
            // 接着访问右子节点
            root = root.right;
        } else { // 左子树不为null，寻找左子树中最右叶子节点，将其后继节点设为当前节点，不然找不到父节点了
            // 不停的从右子树中寻找pre节点
            pre = root.left;
            while (pre.right != null && pre.right != root) { // 因为之前最叶子树pre.right存储了当前子树的根节点，以便当前子树遍历完后，避免找不到父节点的情况
                pre = pre.right;
            }
            // pre为null说明是当前子树第一次遍历；那么刚找完pre节点后，继续往node的左子树遍历
            if (pre.right == null) {
                // 将找到的当前子树最右子节点的后继节点指向node，以便找不到父节点
                pre.right = root;
                root = root.left;
            } else { // pre.right不为null，说明pre.right=node，说明已经遍历到当前子树的最右子树了，需要遍历下一颗树了
                // 将当前子树根节点加入res
                res.add(root.val);

                // 恢复树原来结构
                pre.right = null;

                // 指向右节点，右节点
                root = root.right;
            }
        }
    }
    return res;
}

经典算法小评(2)——Morris树遍历算法

二叉树遍历题解

史上最全遍历二叉树详解

二叉树面试题

30道题搞定大厂算法面试-二叉树

二叉树遍历相关题

102. 二叉树的层序遍历

见上面层序遍历的解法

103. 二叉树的锯齿形层序遍历 medium

题目

你二叉树的根节点 root ，返回其节点值的** 锯齿形层序遍历** 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。输入：root = [3,9,20,null,null,15,7] 输出：[[3],[20,9],[15,7]]

解法 1：借助队列

思路 1：
在普通层序迭代方法（借助队列）的基础上：始终保持队列中顺序为：每层的从左往右

奇数层，从左往右弹出 (pollFirst)，下一偶数层子结点从右往左添加（结点添加到队首 addFirst）
偶数层，从右往左弹出 (pollLast)，下一奇数层子结点从左往右添加（结点添加到队尾 addLast）

思路 2：
在普通层序迭代方法的基础上；始终保持队列中顺序为：每层的从左到右；保存每层节点的 List: levelResuts

奇数层，将弹出的节点，插入到 levelResults 的尾部；从右到左
偶数层，将弹出的节点，插入到 levelResults 的头部；从左到右

代码（思路 2）：

  
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    // 判空
    if (root == null) return allResults;
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点先入队列
    queue.offer(root);
    int level = 1; // 树的层级
    while (!queue.isEmpty()) {
        // 当前层有多少个节点
        int size = queue.size();
        List<Integer> levelResults = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            // 一个个将当前层的节点出队列
            TreeNode node = queue.poll();
            // 出队列的加入到结果List
            // 如果是奇数层的话，一个个加入到最后；如果是偶数层，一个个加入到最前面
            if (level % 2 == 1) {
                levelResults.add(node.val);
            } else {
                levelResults.add(0, node.val);
            }
            // 将出队列节点的的孩子节点加入到临时队列
            TreeNode left = node.left;
            if (left != null) {
                queue.offer(left);
            }
            TreeNode right = node.right;
            if (right != null) {
                queue.offer(right);
            }
        }
        allResults.add(levelResults);
        level++;
    }
    return allResults;
}

解法 2：递归

思路：
和普通的层序遍历类似，只是在添加每层元素到 List 时

是奇数层数，从左到右方向
是偶数层数，从右到左方向

代码：

  
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    // 判空
    if (root == null) return allResults;
    levelOrder(root, 0, allResults);
    return allResults;
}

public void levelOrder(TreeNode root, int level, List<List<Integer>> lists) {
    if (root == null) return;
    // 当前层数和lists相同时，表示刚遍历到该层，需要创建一个List
    if (level == lists.size()) {
        List<Integer> temp = new ArrayList<>();
        lists.add(temp);
    }
    // 根据当前level，怎么添加
    if (level % 2 == 0) { // 奇数，level从0开始，从左到右
        lists.get(level).add(root.val);
    } else { // 偶数，从右到左
        lists.get(level).add(0, root.val);
    }
    // 孩子遍历是一个递归过程，只需要将level+1即可
    levelOrder(root.left, level + 1, lists);
    levelOrder(root.right, level + 1, lists);
}

199. 二叉树的右视图

题目：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解法 1：层序遍历，记录最后一个节点

思路：利用 BFS 进行层次遍历，记录下每层的最后一个元素
代码：

  
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    // 队列记录每层需要遍历的节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) { // 只留最后一个节点
                res.add(node.val);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return res;
}

复杂度：

时间复杂度：O(n)，n 个节点都需要遍历一遍
空间复杂度：O(n)，队列存储 n 个元素

解法 2：DFS 模拟前序遍历（根右左，递归）

思路：

题目是要二叉树每层所有的右节点，问题 1 是怎么知道遍历到了新的一层，问题 2 是怎么找到最右侧的节点

问题 1，用 level 变量来表示当前到了树的哪层，从 0 开始
问题 2，默认的层序遍历是从左到右，要想右开始，那么就返过来，先访问右子树，再访问左子树

代码：

  
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    rightSideView(root, 0, res); // 从根节点开始访问，根节点深度是0
    return res;
}
public void rightSideView(TreeNode root, int level, List<Integer> res) {
    if (root == null) return;
    // 先访问 当前节点，再递归地访问 右子树 和 左子树
    if (level == res.size()) {
        // 访问到了新的一层了
        res.add(root.val);
    }
    rightSideView(root.right, level + 1, res);
    rightSideView(root.left, level + 1, res);
}

复杂度：

树的高度

104. 二叉树的最大深度 easy

题目

给定一个二叉树，找出其最大深度。 二叉树的深度为：根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

1. 递归解法 DFS 深度优先最优解
思路：

可以拆分成子问题：root(最大深度) = max(左节点最大深度, 右节点最大深度) + 1
递推公式：要求 root 的最大深度，就是分别求左子节点最大深度和右子节点最大深度中的最大值，然后加 1
终止条件：是叶子节点

  
// 定义：输入根节点，返回这棵二叉树的最大深度
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 利用定义，计算左右子树的最大深度
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    // 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
    return Math.max(leftMax, rightMax) + 1;
}

复杂度

时间复杂度 O(n)

2. 层序遍历解法 BFS 广度优先

  
public static int maxDepth2(TreeNode root) {
    if (root == null) return 0;
    int depth = 0;
    // 借助队列
    LinkedList<TreeNode> queue = new LinkedList<>();
    // 先将root存进去
    queue.push(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 遍历第一层
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // 存left
            if (node.left != null) {
                queue.offer(node.left);
            }
            // 存right
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        depth++;
    }
    return depth;
}

111. 二叉树的最小深度 easy

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量

解法 1：递归

思路

由于是要求二叉树的最小深度，需要知道子树的深度，所以要在后序位置写代码

  
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    // 后序位置：知道左右子树的的深度
    // 某个节点的left或right子树为空，最小深度为该节点right+1或left+1（即一个节点，如果没有左子树，最小深度为其到右子节点距离）
    // 如果left或right子树都不为空，取他们最小的深度+1
    return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}

543. 二叉树的直径 easy

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

解法 1：递归

思路

树的直径=左子树的深度 + 右子树的深度（这里是不加上自身节点的，所以不用加 1）；要和树的深度是节点个数
在遍历树的后序位置，得到左右子树的最大深度后，更新树的直径 myDiameter=left+right，取 maxDiameter 和 myDiameter 中的最大值赋值给 myDiameter
最后返回 maxDiameter

疑问？
为什么直径可以用 2 颗子树的深度来计算？
这是因为因为没有包括 treeNode 本身，如果包括了本身就会多出来数量 2，不包括就刚刚好等于直径

如下图对于节点 1 来说，它的左子深度为 3，右子树深度为 2，节点 2 的最大深度为 2，节点 3 的最大深度为 1；但对于其直径来说，节点 1 的左边直径 (2)+ 右边直径 (1)=3，刚好等于其两颗子树的最大深度和 2+1=3

  
int maxDiameter = 0;
// 求一颗树的直径长度，其实就是求一个节点左右子树的边之和
public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return maxDiameter;
}
private int maxDepth(TreeNode treeNode) {
    if (treeNode == null) return 0;
    int left = maxDepth(treeNode.left);
    int right = maxDepth(treeNode.right);
    // 后序位置，计算直径和，并记录最大的值
    // 为什么直径可以用2颗子树的深度来计算，这是因为因为没有包括treeNode本身，如果包括了本身就会多出来数量2，不包括就刚刚好等于直径
    int myDiameter = left + right;
    maxDiameter = Math.max(myDiameter, maxDiameter);
    return Math.max(left, right) + 1;
}

递归思路相关题树递归解法相关题

###

二叉树中和为某一值的路径 (一)

题解

递归解法

思路：

递推公式：

root路径= max(左节点(sum-root.val),右节点(sum-root.val))

递归终止条件：

root==null

叶子节点且sum-root.val=0（即存在这样一条路径和为sum）

  
/**
 * 递归解法
 *
 * 1. 递归终止条件，是叶子节点且sum-叶子节点val=0
 *
 * 2. 递推公式：当前节点是否存在该路径(sum) = 左子节点是否存在该路径(sum-当前节点.val) ||
 * 右子节点是否存在该路径(sum-当前节点.val)
 */
public static boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;

    if (root.left == null && root.right == null && sum - root.val == 0) {
        return true;
    }
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    TreeNode node1_0 = new TreeNode(2);
    root.left = node1_0;

    boolean b = hasPathSum(root, 3);
    System.out.println("是否存在路径等于3的=" + b);

}

双栈解法

  
/**
 * 栈辅助解法: 2个栈
 * 1. 一个栈存节点，用来DFS回溯的节点用
 * 2. 一个栈存路径的节点总和
 */
public static boolean hasPathSum2(TreeNode root, int sum) {
    if (root == null) return false;

    // 存回溯的节点
    Stack<TreeNode> stack = new Stack<>();
    // 存路径总和（跟随stack记录到相应节点为止的路径和）
    Stack<Integer> pathVal = new Stack<>();

    stack.push(root);
    pathVal.push(root.val);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();

        Integer curVal = pathVal.pop();
        // 判断是否是叶子节点且是否存在路径等于sum
        if (node.left == null && node.right == null && curVal == sum) {
            return true;
        }
        // 右节点入栈；右节点路径入栈（需加上前面路径的和）
        if (node.right != null) {
            stack.push(node.right);
            pathVal.push(curVal + node.right.val);
        }
        // 左节点入栈；左节点路径入栈（需加上前面路径的和）
        if (node.left != null) {
            stack.push(node.left);
            pathVal.push(curVal + node.left.val);
        }
    }
    return false;
}

对称的二叉树

题目
1. 递归解法

  
/**
 * 递归解法
 */
static boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null) return true;

    return recur(pRoot.left, pRoot.right);
}

// 递归函数功能：判断左右两个结点是否对称相等
private static boolean recur(TreeNode left, TreeNode right) {
    // 可以两个都为空
    if (left == null && right == null) {
        return true;
    }
    // 只有一个为空，必定不对称
    if (left == null || right == null) {
        return false;
    }
    // 节点值不同，必定不对称
    if (left.val != right.val) {
        return false;
    }
    // 每层对应的节点进入递归比较
    return recur(left.left, right.right) && recur(left.right, right.left);
}

2. 层序遍历 + 队列解法

  
/**
 * 思路：<br/> 1. BFS层序遍历 2. 比对是否对称 3. 双队列辅助
 */
static boolean isSymmetrical2(TreeNode pRoot) {
    if (pRoot == null || (pRoot.left == null && pRoot.right == null)) return true; // 单个元素算对称

    LinkedList<TreeNode> queue1 = new LinkedList<>();
    LinkedList<TreeNode> queue2 = new LinkedList<>();

    queue1.offer(pRoot.left);
    queue2.offer(pRoot.right);
    while (!queue1.isEmpty() && !queue2.isEmpty()) {
        TreeNode node1 = queue1.poll();
        TreeNode node2 = queue2.poll();

        // 如果都为null
        if (node1 == null && node2 == null) {
            continue;
        }
        // 某一个为null，不对称
        if (node1 == null || node2 == null) {
            return false;
        }
        // 值不相等
        if (node1.val != node2.val) {
            return false;
        }
        // 左边入队列：先入左，再入右
        queue1.offer(node1.left);
        queue1.offer(node1.right);
        // 右边入队列：先入右，再入左
        queue2.offer(node2.right);
        queue2.offer(node2.left);
    }
    return queue1.isEmpty() && queue2.isEmpty(); // 有一个不为空，代表不对称
}

/**
 * 思路：<br/> 1. BFS层序遍历 2. 比对是否对称 3. 单队列辅助
 */
static boolean isSymmetrical3(TreeNode pRoot) {

    if (pRoot == null || (pRoot.left == null && pRoot.right == null)) return true; // 单个元素算对称

    // BFS通常借助队列实现
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.offer(pRoot.left);
    queue.offer(pRoot.right);

    while (!queue.isEmpty()) {
        // 出队列2个
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        // 表示bfs已经进行到叶子结点了
        if (left == null && right == null) {
            continue;
        }
        // 某一个为null，不对称
        if (left == null || right == null) {
            return false;
        }
        // 值不相等
        if (left.val != right.val) {
            return false;
        }
        // 对下一层的每个结点，都放入队列中
        // 注意放入队列的顺序，左子结点的左子结点、右子结点的右子结点、左结点的右子结点、右结点的左子结点放入队列。
        queue.offer(left.left);
        queue.offer(right.right);
        queue.offer(left.right);
        queue.offer(right.left);
    }
    return true;
}

合并二叉树

  
/**
 * 递归解法
 * 1. 递归结束条件
 *  - t1==null且t2==null，返回null
 *  - t1==null且t2!=null，返回t2
 *  - t1!=null且t1==null，返回t1
 * 2. 递推公式
 *  - 先合并2颗树的根节点值t1.val+t2.val赋值为新的节点node
 *  - 合并t1和t2的左节点，作为node的left
 *  - 合并t1和t2的右节点，作为node的right
 */
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null) return t2;
    if (t2 == null) return t1;

    TreeNode node = new TreeNode(t1.val+t2.val);
    node.left = mergeTrees(t1.left,t2.left);
    node.right = mergeTrees(t1.right,t2.right);
    return node;
}

二叉树的镜像

  
public TreeNode Mirror(TreeNode pRoot) {
    if (pRoot == null) return null;
    // 镜像左子树
    TreeNode mirrorLeft = Mirror(pRoot.left);
    // 镜像右子树
    TreeNode mirrorRight = Mirror(pRoot.right);
    // 交换
    pRoot.left = mirrorRight;
    pRoot.right = mirrorLeft;
    return pRoot;
}

判断是不是二叉搜索树

递归

  
public boolean isValidBST(TreeNode root) {
    return BST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
// left为当前左子树最大值，right为当前右子树最小值
private boolean BST(TreeNode root, long left, long right) {
    // 递归终止条件
    if (root == null) return true;
    // 如果当前节点小于等于左子树节点最大值或者大于等于右子树节点最小值，则不合法
    if (root.val <= left || root.val >= right) {
        return false;
    }
    // 往左子树递归时，left不变，对应右子树由于要考虑当前节点，right变为root.val,同理考虑右子树
    return BST(root.left, left, root.val) && BST(root.right, root.val, right);
}

中序遍历法

  
public boolean isValidBST2(TreeNode root) {
    if (root == null) return true;
    // 借助List存储中序遍历后的val
    List<Integer> list = new ArrayList<>();
    // 借助栈存储临时节点
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || root != null) {
        // 先将所有左子节点入栈
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // 弹栈
        TreeNode node = stack.pop();
        // 访问节点
        list.add(node.val);
        // 处理右子节点
        root = node.right;
    }
    // 遍历list时候升序
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i + 1) < list.get(i)) {
            return false;
        }
    }
    return true;
}

判断是不是平衡二叉树

递归解法

  
// 平衡二叉树：左右子树的高度相差绝对值不超过1
public static boolean IsBalanced_Solution(TreeNode root) {
    if (root == null) return true;
    return deep(root) != -1;
}
// 返回树的高度
private static int deep(TreeNode root) {
    if (root == null) return 0;
    // 左子树高度
    int left = deep(root.left);
    if (left == -1) return -1; // 已经出现了左右子树高度绝对值大于1了，已经不是平衡二叉树了。不需要递归了
    // 右子树高度
    int right = deep(root.right); // 已经出现了左右子树高度绝对值大于1了，已经不是平衡二叉树了。不需要递归了
    if (right == -1) return -1;
    // 左右子树超过1了，返回-1；否则返回树的高度
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}

二叉搜索树的最近公共祖先

BM37 二叉搜索树的最近公共祖先题解

  
public int lowestCommonAncestor(TreeNode root, int p, int q) {
    int val = root.val;
    if (val > p && val > q) { // 在root左边
        return lowestCommonAncestor(root.left, p, q);
    } else if (val < p && val < q) { // 在root右边
        return lowestCommonAncestor(root.right, p, q);
    } else { // 分布在root的左右两边
        return val;
    }
}

在二叉树中找到两个节点的最近公共祖先

题目
 题解

  
public TreeNode lowestCommonAncestorNode(TreeNode root, int o1, int o2) {
    // 如果为叶子节点，返回null
    if (root == null) return null;
    // 如果o1或o2等于root，那么公共祖先为o1或o2
    if (root.val == o1 || root.val == o2) return root;
    // 递归
    TreeNode left = lowestCommonAncestorNode(root.left, o1, o2);
    TreeNode right = lowestCommonAncestorNode(root.right, o1, o2);
    if (left == null) return right;
    if (right == null) return left;
    return root;
}
/**
 * 递归解法
 */
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
    return lowestCommonAncestorNode(root, o1, o2).val;
}

105. 从前序与中序遍历序列构造二叉树根据前序和中序重建二叉树 medium

题解
题目：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]

思路：

前序遍历是根左右，可以确定第 1 个节点是根节点；中序遍历是左根右
根据前序第 1 个节点为根，再从中序中找到该节点，该节点左边是左子树，右边是右子树
进而将左子树和右子树划分成了子问题，左右子树递归重复上述流程
1. 关键的怎么确定左/右子树的数组范围

演示：

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] 首先根据 preorder 找到根节点是 3
然后根据根节点将 inorder 分成左子树和右子树左子树 inorder [9]
右子树 inorder [15,20,7]
把相应的前序遍历的数组也加进来左子树 preorder[9] inorder [9]
右子树 preorder[20 15 7] inorder [15,20,7]
现在我们只需要构造左子树和右子树即可，成功把大问题化成了小问题然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可

题解：详细通俗的思路分析，多解法

解法 1：递归，切分生成新的数组不推荐

根据前序找到根节点，然后在中序中找到根节点对应的索引
将中序左右划分为左右子树，重复 1~2，直到碰到叶子节点

  
// 解法1：调用系统copy数组
public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 递归结束条件
    if (preorder.length == 0 || inorder.length == 1) {
        return null;
    }
    // 构建root
    TreeNode treeNode = new TreeNode(preorder[0]);
    for (int i = 0; i < inorder.length; i++) {
        // 找到根节点
        if (preorder[0] == inorder[i]) {
            // inorder左边是左子树（左闭右开）
            int[] leftPre = Arrays.copyOfRange(preorder, 1, i + 1);
            int[] leftIn = Arrays.copyOfRange(inorder, 0, i);
            treeNode.left = buildTree(leftPre, leftIn);
            // inorder右边是右子树
            int[] rightPre = Arrays.copyOfRange(preorder, i + 1, preorder.length);
            int[] rightIn = Arrays.copyOfRange(inorder, i + 1, inorder.length);
            treeNode.right = buildTree(rightPre, rightIn);
            break;
        }
    }
    return treeNode;
}

// 解法2：手写copy数组
public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 递归结束条件
    if (preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    TreeNode rootNode = new TreeNode(preorder[0]);
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == rootVal) {
            rootNode.left = buildTree(subArray(preorder, 1, i + 1), subArray(inorder, 0, i));
            rootNode.right = buildTree(subArray(preorder, i + 1, preorder.length), subArray(inorder, i + 1, inorder.length));
            break;
        }
    }
    return rootNode;
}
/**
 * 截取数组，包括start，不包括end（左闭右开）
 */
public int[] subArray(int[] src, int start, int end) {
    int[] temp = new int[end - start];
    for (int i = 0; i < end - start; i++) {
        temp[i] = src[start + i];
    }
    return temp;
}

不足：每次都需要生成新的数组。

解法 2：递归，在原数组基础上推荐

根据 preorder 数组第 0 索引位置为根节点，然后在 inorder 中找到该节点的索引（遍历 or 哈希表？），索引的左边为左子树，右边为右子树
根节点的左子树为 inorder 数组根节点左边，右子树为 inorder 根节点的右边，递归重复该操作
1. 计算子问题时需要的变量
  1. inorderIndex，preorder 根节点再 inorderIndex 的索引，可通过遍历或哈希表获取该值
  2. preStart，preEnd 指向 preorder 每个子数组的起始位置和结束位置
  3. inStart，inEnd 指向 inorder 每个子数组的起始位置和结束位置

不足：需要遍历计算根节点索引：

  
public TreeNode buildTree10(int[] preorder, int[] inorder) {
    // 索引是包括数组的最后一个
    return buildChildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

public TreeNode buildChildTree(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR) {
    // 递归结束条件
    if (preL > preR || inL > inR) {
        return null;
    }
    // 计算根节点在inorder位置，遍历？
    int pivot = 0;
    for (int i = inL; i <= inR; i++) {
        if (preorder[preL] == inorder[i]) {
            pivot = i;
            break;
        }
    }
    // 构建根节点
    TreeNode rootNode = new TreeNode(preorder[preL]);
    // 构建左、右子树
    // 要构建rootNode的左子树，得知道preorder和inorder数组从什么位置开始取值
    // 前序和中序他们左+根两部分长度是一样的，所以我们根据inorder的根，就可以计算出preorder的左开始位置：长度inorder的根索引-inL开始位置
    int leftPreR = preL + pivot - inL;
    rootNode.left = buildChildTree(preorder, preL + 1, leftPreR, inorder, inL, pivot - 1);
    int rightPreL = leftPreR + 1;
    rootNode.right = buildChildTree(preorder, rightPreL, preR, inorder, pivot + 1, inR);
    return rootNode;
}

根节点索引存 Map 解法：最优解

用哈希表将 inorder 按 key 为值，value 为索引将 inorder 存储起来
根据 preorder 第 0 处索引根节点，去 inorder 中找到该根节点的索引，其左边是左子树，右边是右子树
关键是如何通过根节点的索引计算出拆分后子数组的索引
1. 根节点在 inorder 索引 pivot
2. 左孩子 preorder 索引：preL，preL+pivot-inL；右孩子 preorder 索引：preL+pivot-intL+1
3. 左孩子 inorder 索引：inL，pivot-1；右孩子 inorder 索引：pivot+1,inR

  
public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return buildChildTree2(preorder, 0, preorder.length - 1, 0, inorder.length - 1, map);
}
// 有了哈希表，就不需要inorder参与计算根节点位置了
private TreeNode buildChildTree2(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> map) {
    // 结束条件
    if (preL > preR) {
        return null;
    }
    // 直接从哈希表map中获取根节点在inorder的索引
    int pivot = map.get(preorder[preL]);
    // 构建根节点
    TreeNode root = new TreeNode(preorder[preL]);
    int leftPreEnd = preL + pivot - inL;
    root.left = buildChildTree2(preorder, preL + 1, leftPreEnd, inL, pivot - 1, map);
    root.right = buildChildTree2(preorder, leftPreEnd + 1, preR, pivot + 1, inR, map);
    return root;
}

解法 3：迭代

二叉搜索树与双向链表

题目

递归解法（pre 指针）

  
TreeNode head;
TreeNode pre;

/**
 * 递归法
 */
public TreeNode Convert2(TreeNode pRootOfTree) {

    if (pRootOfTree == null) return null;

    // 左
    Convert2(pRootOfTree.left);

    // 根
    if (head == null) {
        head = pRootOfTree;
    }

    pRootOfTree.left = pre;
    if (pre != null) {
        pre.right = pRootOfTree;
    }
    pre = pRootOfTree;

    // 右
    Convert2(pRootOfTree.right);
    return head;
}

迭代解法（栈 +pre 指针）

  
/**
 * 二叉搜索树与双向链表 思路：
 *
 * 1. 是一个中序遍历 2.
 */
public static TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) return null;


    Stack<TreeNode> stack = new Stack<>();

    TreeNode head = null;
    TreeNode pre = null;

    while (!stack.isEmpty() || pRootOfTree != null) {

        // 将所有的左节点入栈
        while (pRootOfTree != null) {
            stack.push(pRootOfTree);
            pRootOfTree = pRootOfTree.left;
        }

        TreeNode node = stack.pop();

        // 找到根节点
        if (head == null) {
            head = node;
        }

        // 当前节点与上一节点建立连接，将pre设置为当前值
        node.left = pre;
        if (pre != null) {
            pre.right = node;
        }
        System.out.println("pre=" + (pre == null ? "null" : pre.val) + "，node=" + node.val);
        pre = node;

        // 看是否有右子节点，有的话继续处理右子节点
        pRootOfTree = node.right;
    }
    return head;
}

序列化二叉树

题目

蛇形打印二叉树

数据结构和算法, 树

数据结构和算法树

本文由作者按照 CC BY 4.0 进行授权

二叉树基础

什么是二叉树？

二叉树种类

完全二叉树

满二叉树

二叉排序树

平衡二叉树 AVL 树

红黑树

哈夫曼树

二叉树的遍历 必须掌握

二叉树遍历介绍

二叉树遍历的四种方式

二叉树遍历框架

二叉树前中后序遍历理解

二叉树解题通用思路

二叉树前序遍历 DFS

前序遍历 - 递归法

前序遍历 - 迭代法

二叉树中序遍历

中序遍历 - 递归法

中序遍历 - 迭代法（借助栈）

二叉树后序遍历

后序遍历 - 递归法

后序遍历 - 迭代 - 尾插法

后续遍历 - 迭代解法（正序）

BFS: 二叉树层序遍历，不需按层输出

BFS: 二叉树层序遍历，按层输出（medium）

1、队列迭代解法

2、递归解法

morris 遍历

中序 Morris 遍历

二叉树遍历题解

二叉树面试题

二叉树遍历相关题

102. 二叉树的层序遍历

103. 二叉树的锯齿形层序遍历 medium

解法 1：借助队列

解法 2：递归

199. 二叉树的右视图

解法 1：层序遍历，记录最后一个节点

解法 2：DFS 模拟前序遍历（根右左，递归）

树的高度

104. 二叉树的最大深度 easy

111. 二叉树的最小深度 easy

解法 1：递归

543. 二叉树的直径 easy

解法 1：递归

递归思路相关题 树递归解法相关题

二叉树中和为某一值的路径 (一)

对称的二叉树

合并二叉树

二叉树的镜像

判断是不是二叉搜索树

递归

中序遍历法

判断是不是平衡二叉树

二叉搜索树的最近公共祖先

在二叉树中找到两个节点的最近公共祖先

105. 从前序与中序遍历序列构造二叉树 根据前序和中序重建二叉树 medium

解法 1：递归，切分生成新的数组 不推荐

解法 2：递归，在原数组基础上 推荐

解法 3：迭代

二叉搜索树与双向链表

序列化二叉树

蛇形打印二叉树

热门标签

二叉树的遍历必须掌握

递归思路相关题树递归解法相关题

105. 从前序与中序遍历序列构造二叉树根据前序和中序重建二叉树 medium

解法 1：递归，切分生成新的数组不推荐

解法 2：递归，在原数组基础上推荐