題目描述 輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。 解題思路 基礎知識 前序遍歷：根結點 > 左子樹 > ...
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。
/// 1 /// / \ /// 2 3 /// / / \ /// 4 5 6 /// \ / /// 7 8
解題思路
基礎知識
前序遍歷：根結點 ---> 左子樹 ---> 右子樹
中序遍歷：左子樹---> 根結點 ---> 右子樹
後序遍歷：左子樹 ---> 右子樹 ---> 根結點
層次遍歷：只需按層次遍歷即可
例如：
前序遍歷：1 2 4 7 3 5 6 8
中序遍歷：4 7 2 1 5 3 8 6
後序遍歷：7 4 2 5 8 6 3 1
層次遍歷：1 2 3 4 5 6 7 8
前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
中序遍歷（LDR）是二叉樹遍歷的一種，也叫做中根遍歷、中序周游。在二叉樹中，中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
二叉樹的什麼什麼遍歷，其實也是很好記的，就是根在呢就是什麼遍歷，在前就是前遍歷，中就是中序遍歷，後就是後序遍歷，其他的是層次遍歷。
解題：
根據前序遍歷，可以知道根節點（1），根據中序遍歷可以知道左子樹（4,7,2）和右子樹（5,3,8,6）。找到左右子樹之後，我們可以以相同的方式找到左右子樹，也就是說這是一個遞歸的過程。根>左>右。
代碼實現
二叉樹
/// <summary> /// 二叉樹 /// </summary> public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } }
前序遍歷：根結點 ---> 左子樹 ---> 右子樹
public static void PreNode(TreeNode node, List<int> treeList) { if (node != null) { treeList.Add(node.val); PreNode(node.left, treeList); PreNode(node.right, treeList); } }
中序遍歷：左子樹---> 根結點 ---> 右子樹
public static void MidNode(TreeNode node, List<int> treeList) { if (node != null) { MidNode(node.left, treeList); treeList.Add(node.val); MidNode(node.right, treeList); } }
後序遍歷：左子樹 ---> 右子樹 ---> 根結點
public static void EndNode(TreeNode node, List<int> treeList) { if (node != null) { EndNode(node.left, treeList); EndNode(node.right, treeList); treeList.Add(node.val); } }
層次遍歷：只需按層次遍歷即可。思路：根據層次遍歷的順序，每一層都是從左到右的遍歷輸出，藉助於一個隊列。先從根節點入隊，將其出隊訪問，如果當前節點的左節點不為空左節點入隊，如果當前右節點部位空右節點入隊。所以出隊順序是從左到右。
public static void LevelNode(TreeNode node, List<int> treeList) { if (node != null) { Queue<TreeNode> queue = new Queue<TreeNode>(); queue.Enqueue(node); TreeNode currentNode = null; while (queue.Count > 0) { currentNode = queue.Dequeue(); treeList.Add(currentNode.val); if (currentNode.left != null) { queue.Enqueue(currentNode.left); } if (currentNode.right != null) { queue.Enqueue(currentNode.right); } } } }
二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。思路：根據前序遍歷找到根，根據中序遍歷找到左右子樹，依次遞歸。歸結：根 > 左 > 右
public static TreeNode Tree(List<int> preTree, List<int> midTree) { if (preTree == null || preTree.Count() == 0 || midTree == null || midTree.Count() == 0) { return null; } //根節點 int rootTree = preTree[0]; //移除根節點 preTree.RemoveAt(0); TreeNode treeNode = new TreeNode(rootTree); //左右子樹 List<int> leftTree = null; List<int> tempList = new List<int>(); bool isTree = false; foreach (var item in midTree) { tempList.Add(item); if (item == rootTree) { isTree = true; tempList.Remove(item); leftTree = tempList; tempList = new List<int>(); } } if (!isTree) { Console.WriteLine("不是正確的樹"); return null; } List<int> rightTree = tempList; //遞歸左右節點 treeNode.left = Tree(preTree, leftTree); treeNode.right = Tree(preTree, rightTree); return treeNode; }
測試
普通二叉樹
/// <summary> /// 普通二叉樹 /// 1 /// / \ /// 2 3 /// / / \ /// 4 5 6 /// \ / /// 7 8 /// </summary> [Fact] public void Common() { int[] preTree = { 1, 2, 4, 7, 3, 5, 6, 8 }; int[] midTree = { 4, 7, 2, 1, 5, 3, 8, 6 }; TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList()); List<int> result = new List<int>(); Coding004.PreNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result)); result.Clear(); Coding004.MidNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result)); }
所有結點都沒有右子結點
/// <summary> /// 所有結點都沒有右子結點 /// 1 /// / /// 2 /// / /// 3 /// </summary> [Fact] public void Right() { int[] preTree = { 1, 2, 3 }; int[] midTree = { 3, 2, 1 }; TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList()); List<int> result = new List<int>(); Coding004.PreNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result)); result.Clear(); Coding004.MidNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result)); }
所有結點都沒有左子結點
/// <summary> /// 所有結點都沒有左子結點 /// 1 /// \ /// 2 /// \ /// 3 /// \ /// /// \ /// 5 /// </summary> [Fact] public void Left() { int[] preTree = { 1, 2, 3, 4, 5 }; int[] midTree = { 1, 2, 3, 4, 5 }; TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList()); List<int> result = new List<int>(); Coding004.PreNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result)); result.Clear(); Coding004.MidNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result)); }
樹中只有一個結點
/// <summary> /// 樹中只有一個結點 /// </summary> [Fact] public void One() { int[] preTree = { 1 }; int[] midTree = { 1 }; TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList()); List<int> result = new List<int>(); Coding004.PreNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result)); result.Clear(); Coding004.MidNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result)); }
完全二叉樹
/// <summary> /// 完全二叉樹 /// 1 /// / \ /// 2 3 /// / \ / \ /// 4 5 6 7 /// </summary> [Fact] public void All() { int[] preTree = { 1, 2, 4, 5, 3, 6, 7 }; int[] midTree = { 4, 2, 5, 1, 6, 3, 7 }; TreeNode tree = Coding004.Tree(preTree.ToList(), midTree.ToList()); List<int> result = new List<int>(); Coding004.PreNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(preTree), JsonConvert.SerializeObject(result)); result.Clear(); Coding004.MidNode(tree, result); Assert.Equal(JsonConvert.SerializeObject(midTree), JsonConvert.SerializeObject(result)); }
想入非非：擴展思維，發揮想象
1. 熟悉二叉樹
2. 熟悉二叉樹的幾種遍歷
3. 熟悉隊列先進先出
4. 熟悉遞歸
