重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

二叉树：二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。在二叉树中最重要的操作是遍历，即按照某一顺序访问树中的所有结点。

树的遍历方式：前序遍历：先访问根节点，再访问左子结点，最后访问右子结点；（根左右）中序遍历：先访问左子结点，再访问根结点，最后访问右子结点；（左根右）后序遍历：先访问左子结点，再访问右子结点，最后访问根结点；（左右根）

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

分别找到了左、右子树的前序遍历序列和中序遍历序列，我们就可以用同样的方法分别去构建左右子树，这是一个递归的过程。

my ugly code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


using System;
using System.Collections.Generic;

/*
public class TreeNode
{
	public int val;
	public TreeNode left;
	public TreeNode right;

	public TreeNode (int x)
	{
		val = x;
	}
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pre int整型一维数组 
     * @param tin int整型一维数组 
     * @return TreeNode类
     */
   public TreeNode reConstructBinaryTree(List<int> pre, List<int> vin)
   {
       // write code here
       if (pre == null || vin == null || pre.Count != vin.Count || pre.Count <= 0 || vin.Count <= 0)
       {
           return null;
       }

       return ConstructCore(pre, 0, pre.Count - 1, vin, 0, vin.Count - 1);
   }

    TreeNode ConstructCore(List<int> Preorder, int startPre, int endPre, List<int> Inorder, int startIn, int endIn)
    {
        // 停止递归的条件
        if (startPre > endPre || startIn > endIn)
        {
            return null;
        }

        // 前序遍历数组的第一个元素， 即是根节点
        TreeNode tree = new TreeNode(Preorder[startPre]);
        for (int i = startIn; i <= endIn; i++)
        {
            if (Inorder[i] == Preorder[startPre])
            {
                // i - startIn 是 中序遍历序列中左子树节点的个数

                // left sub tree
                tree.left = ConstructCore(Preorder, startPre + 1, startPre + i - startIn, Inorder, startIn, i - 1);

                // right sub tree
                tree.right = ConstructCore(Preorder, i - startIn + startPre + 1, endPre, Inorder, i + 1, endIn);
            }
        }
        return tree;
    }
}

测试代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


// 层次遍历二叉树
public static IList<IList<int>> LevelOrder(TreeNode root)
{
    var result = new List<IList<int>>();
    LevelOrder(root, 0, result);
    return result;
}

public static void LevelOrder(TreeNode node, int level, List<IList<int>> result)
{
    if (node == null) return;
    // 判断当前层是否有节点集合， 如果没有就创建并存入结果结合
    IList<int> levelResult;
    if (result.Count > level)
    {
        levelResult = result[level];
    }
    else
    {
        levelResult = new List<int>();
        result.Add(levelResult);
    }

    // 存储当前节点的值
    levelResult.Add(node.val);

    // 递归左节点
    LevelOrder(node.left, level + 1, result);

    // 递归右节点
    LevelOrder(node.right, level + 1, result);
}

static void Main(string[] args)
{
    var treePre = new List<int> {1, 2, 4, 7, 3, 5, 6, 8};
    var treeIn = new List<int> {4, 7, 2, 1, 5, 3, 8, 6};

    var tree = reConstructBinaryTree(treePre, treeIn);

    var levelOrderRes = LevelOrder(tree);

    foreach (var item in levelOrderRes)
    {
        foreach (var ele in item)
        {
            Console.Write(ele);
            Console.Write(" ");
        }
        Console.WriteLine();
    }
    Console.ReadLine();
}

复杂度分析： 时间复杂度 O(N)：其中 N为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N)。递归共建立 N个节点，每层递归中的节点建立、搜索操作占用 O(1)，因此使用 O(N) 时间。空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间。最差情况下，树退化为链表，递归深度达到 NN ，占用 O(N) 额外空间；最好情况下，树为满二叉树，递归深度为logN ，占用 O(log N) 额外空间。

高手代码赏析

解题思路

不用递归的话，另外很巧妙的办法是用了迭代法；

迭代法是一种非常巧妙的实现方法，坦白说，也不是很好理解。

对于前序遍历中的任意两个连续节点 u和 v，根据前序遍历的流程，我们可以知道 u和 v 只有两种可能的关系：

v是 u 的左儿子。这是因为在遍历到 u 之后，下一个遍历的节点就是 u 的左儿子，即 v；
u没有左儿子，并且 v是 u 的某个祖先节点（或者 u 本身）的右儿子。如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。如果 u没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且 u 不在它的右儿子的子树中）的节点 ua，那么 v 就是 ua 的右儿子。

算法

我们归纳出上述例子中的算法流程：

我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；
无论是哪一种情况，我们最后都将当前的节点入栈。

具体细节可参考 leetcode 重建二叉树- 迭代法题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

文章目录

重建二叉树

题目描述

思路

测试代码

高手代码赏析

解题思路