剑指 Offer 07. 重建二叉树

前序,中序列表构建二叉树思路:

  1. 返回的是一颗二叉树,所以每一次递归都需要构建一个TreeNode

  2. 构建TreeNode需要value, 前序遍历可以提供当前构建TreeNode的Val

  3. preOrder[0]将中序分成左右两子树,所以递归终止条件就是 if not inorder: return None

  4. 递归路径:

    1) 左子树好说,因为preorder[0]是root,preorder[1]就是左子树的root

    2) 但是右子树是很难找的,为了找右子树,将遍历过的左子树节点 preorder都 pop(0),这样保证遍历右节点的时候,preorder只剩右子树元素了。

原文地址:https://www.cnblogs.com/ChevisZhang/p/13660457.html