一些经典的二叉树练习题，帮助理解掌握二叉树的各种遍历方法和递归地解决问题的思路。

二叉树练习

二叉树节点定义

• java

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

• python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

利用中序和后序遍历序列重建二叉树

给定一棵树的中序和后序遍历结果，构造二叉树。

注意：您可以假定树中不存在重复项。

例如，给定

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

返回以下二叉树：

  3
 / \
9  20
  /  \
 15   7

java 参考代码：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(0, postorder, 0, postorder.length - 1, map);
    }

    private TreeNode build(int si, int[] post, int sp, int ep, HashMap<Integer, Integer> map) {
        if (sp > ep) {
            return null;
        }
        TreeNode root = new TreeNode(post[ep]);
        int idx = map.get(root.val);
        int leftLen = idx - si;
        root.left = build(si, post, sp, sp + leftLen - 1, map);
        root.right = build(idx + 1, post, sp + leftLen, ep - 1, map);
        return root;
    }
}

python 参考代码：

from typing import List


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder or len(inorder) != len(postorder):
            return

        indices = {v: i for i, v in enumerate(inorder)}
        return self.build(0, postorder, 0, len(postorder) - 1, indices)

    def build(self, si: int, post: List[int], sp: int, ep: int,
              indices: dict) -> TreeNode:
        if sp > ep:
            return

        root = TreeNode(post[ep])
        idx = indices[root.val]
        llen = idx - si

        root.left = self.build(si, post, sp, sp + llen - 1, indices)
        root.right = self.build(idx + 1, post, sp + llen, ep - 1, indices)

        return root

利用前序和中序遍历序列重建二叉树

给定一棵树的前序和中序遍历结果，构造二叉树。

注意：您可以假定树中不存在重复项。

例如，给定

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

返回以下二叉树：

  3
 / \
9  20
  /  \
 15   7

java 参考代码：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(0, preorder, 0, preorder.length - 1, map);
    }

    private TreeNode build(int si, int[] pre, int sp, int ep,
                           HashMap<Integer, Integer> map) {
        if (sp > ep) {
            return null;
        }
        TreeNode root = new TreeNode(pre[sp]);
        int idx = map.get(root.val);
        int leftLen = idx - si;
        root.left = build(si, pre, sp + 1, sp + leftLen, map);
        root.right = build(idx + 1, pre, sp + leftLen + 1, ep, map);
        return root;
    }
}

python 参考代码：

from typing import List


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder or len(preorder) != len(inorder):
            return

        indices = {v: i for i, v in enumerate(inorder)}
        return self.build(preorder, 0, len(preorder) - 1, 0, indices)

    def build(self, pre: List[int], sp: int, ep: int, si: int,
              indices: dict) -> TreeNode:
        if sp > ep:
            return

        root = TreeNode(pre[sp])
        idx = indices[root.val]
        llen = idx - si

        root.left = self.build(pre, sp + 1, sp + llen, si, indices)
        root.right = self.build(pre, sp + llen + 1, ep, idx + 1, indices)

        return root

填充每个节点的下一个右侧节点指针

您会得到一棵完美的二叉树，其中所有叶子都在同一水平上，每个父级都有两个孩子。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充每个 next 指针以指向其下一个右节点。如果没有下一个右节点，则 next 指针应设置为 NULL。

最初，所有 next 指针都设置为 NULL。

Follow up:

• 您只能使用常量的额外空间。
• 递归方法很好，您可以假定隐式堆栈空间不算作此问题的额外空间。

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: 给定上面完美的二叉树（图A），您的函数应该填充每个下一个指针，
以指向其下一个右节点，如图B所示。序列化的输出按层次顺序排列，与下一个指针相连，
并带有 '＃' 表示每个层次的结束。

限制条件：

• 给定树中的节点数少于4096。
• -1000 <= node.val <= 1000

java 参考代码：

/**
 * Definition for a Node.
 * class Node {
 *     public int val;
 *     public Node left;
 *     public Node right;
 *     public Node next;
 *
 *     public Node() {}
 *
 *     public Node(int _val) {
 *         val = _val;
 *     }
 *
 *     public Node(int _val, Node _left, Node _right, Node  * _next) {
 *         val = _val;
 *         left = _left;
 *         right = _right;
 *         next = _next;
 *     }
 * };
 */

class Solution {
    public Node connect(Node root) {
        Node levelStart = root;
        while (levelStart != null) {
            Node cur = levelStart;
            while (cur != null) {
                if (cur.left != null) {
                    cur.left.next = cur.right;
                    if (cur.next != null) {
                        cur.right.next = cur.next.left;
                    }
                }
                cur = cur.next;
            }
            levelStart = levelStart.left;
        }
        return root;
    }
}

python 参考代码：

# Definition for a Node.
# class Node:
#     def __init__(self,
#                  val: int = 0,
#                  left: 'Node' = None,
#                  right: 'Node' = None,
#                  next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return

        cur = root
        while cur.left:
            head = cur.left

            while cur:
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next

            cur = head

        return root

填充每个节点的下一个右侧节点指针II

给定一棵二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充每个 next 指针以指向其下一个右节点。如果没有下一个右节点，则 next 指针应设置为 NULL。

最初，所有 next 指针都设置为 NULL。

Follow up:

• 您只能使用常量的额外空间。
• 递归方法很好，您可以假定隐式堆栈空间不算作此问题的额外空间。

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: 给定上面的二叉树（图A），您的函数应该填充每个下一个指针，
以指向其下一个右节点，如图B所示。序列化的输出按层次顺序排列，与下一个指针相连，
并用 '＃' 表示 每个层次的结尾。

限制条件：

• 给定树中的节点数少于6000。
• -100 <= node.val <= 100

java 参考代码：

class Solution {
    public Node connect(Node root) {
        Node nextHeadDummy = new Node(0);
        Node nextLevelCur = nextHeadDummy;
        Node cur = root;
        while (cur != null) {
            while (cur != null) {
                if (cur.left != null) {
                    nextLevelCur.next = cur.left;
                    nextLevelCur = nextLevelCur.next;
                }
                if (cur.right != null) {
                    nextLevelCur.next = cur.right;
                    nextLevelCur = nextLevelCur.next;
                }
                cur = cur.next;
            }
            cur = nextHeadDummy.next;
            nextHeadDummy.next = null;
            nextLevelCur = nextHeadDummy;
        }
        return root;
    }
}

python 参考代码：

# Definition for a Node.
# class Node:
#     def __init__(self,
#                  val: int = 0,
#                  left: 'Node' = None,
#                  right: 'Node' = None,
#                  next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return

        cur = root
        while cur:
            head, pre = None, None

            while cur:
                if cur.left:
                    if pre:
                        pre.next = cur.left
                    else:
                        head = cur.left
                    pre = cur.left

                if cur.right:
                    if pre:
                        pre.next = cur.right
                    else:
                        head = cur.right
                    pre = cur.right

                cur = cur.next

            cur = head

        return root

二叉树的最低共同祖先

给定二叉树，在树中找到两个给定节点的最低公共祖先（LCA）。

根据Wikipedia上LCA的定义：“最低的共同祖先被定义为两个节点p和q之间的关系，这是T中同时具有p和q作为后代的最低节点（我们允许一个节点成为其自身的后代）。 ”

给定以下二叉树：root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be
a descendant of itself according to the LCA definition.

注意：

• 所有节点的值都是唯一的。
• p和q不同，并且两个值都将存在于二叉树中。

java 参考代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

python 参考代码：

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left or right

二叉树的序列化与反序列化

序列化是将数据结构或对象转换为位序列的过程，以便可以将其存储在文件或内存缓冲区中，或者通过网络连接进行传输，以便稍后在相同或另一个计算机环境中进行重构。

设计一种用于对二叉树进行序列化和反序列化的算法。序列化/反序列化算法的工作方式没有任何限制。您只需要确保可以将二叉树序列化为字符串，并且可以将该字符串反序列化为原始树结构。

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

说明：上面的格式与 LeetCode 序列化二叉树的方式相同。您不一定需要遵循这种格式，因此请发挥创造力并自己提出不同的方法。

注意：不要使用类成员/全局/静态变量来存储状态。您的序列化和反序列化算法应该是无状态的。

java 参考代码：

class Codec {
    private static final String DELIMITER = ",";
    private static final String PADDING = "$";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(PADDING).append(DELIMITER);
            return;
        }
        sb.append(root.val).append(DELIMITER);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> queue = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
        return deserialize(queue);
    }

    private TreeNode deserialize(LinkedList<String> queue) {
        String val = queue.poll();
        if (PADDING.equals(val)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

python 参考代码：

from typing import List


class Codec:
    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.

        Args:
            root (TreeNode): the root of tree

        Returns:
            str: a serial str of binary tree
        """
        res = []
        self._serial(root, res)
        return ','.join(res)

    def _serial(self, root: TreeNode, res: List[str]) -> None:
        if not root:
            res.append('#')
            return

        res.append(str(root.val))
        self._serial(root.left, res)
        self._serial(root.right, res)

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.

        Args:
            data (str): a serial str of binary tree

        Returns:
            TreeNode: the root of tree
        """
        data = data.split(',')
        data.reverse()
        return self._deserial(data)

    def _deserial(self, data: List[str]) -> TreeNode:
        val = data.pop()
        if val == '#':
            return

        root = TreeNode(int(val))
        root.left = self._deserial(data)
        root.right = self._deserial(data)

        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

References

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/942/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/943/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/994/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/1016/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/932/

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/