刷算法題（4）——JZ4 重建二叉樹_牛客

一、題目

題目描述

輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

示例1

輸入

複制

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
           

傳回值

複制

{1,2,5,3,4,6,7}
           

法一：遞歸，JAVA，數組

思路：遞歸過程，通過前序數組找到二叉樹的根結點，再通過中序數組分出二叉樹的左右子樹，重複該過程直到數組沒有元素

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//法一：遞歸，數組
public class Solution {
    public int[] copyOfrange(int []array,int from,int to)
    {
        int[] result=new int[to-from];
        for(int i=from,j=0;i<to;i++,j++)
            result[j]=array[i];
        return result;
    }
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0) return null;
        TreeNode root=new TreeNode(pre[0]);
        
        for(int i=0;i<in.length;i++)
        {
            if(pre[0]==in[i])
            {
                //java自帶函數Array.copyOfrange，需要包import java.util.Arrays;
                //root.left=reConstructBinaryTree(Array.copyOfrange(pre,1,i+1),Array.copyOfrange(in,0,i));
                //root.right=reConstructBinaryTree(Array.copyOfrange(pre,i+1,pre.length),Array.copyOfrange(in,i+1,in.length));
                
                //自己寫的數組複制函數
                root.left=reConstructBinaryTree(copyOfrange(pre,1,i+1),copyOfrange(in,0,i));
                root.right=reConstructBinaryTree(copyOfrange(pre,i+1,pre.length),copyOfrange(in,i+1,in.length));
            }
        }
        return root;
    }
}
           

法二：遞歸，JAVA，List

//重建二叉樹，法二：遞歸，List
public static TreeNode Tree(List<int> preTree,List <int>midTree)
{
	if(preTree==null||preTree.Count==0||midTree==null||midTree.Count==0)
		return null;
	
	int i=1;

	//根結點
	int rootTree=preTree[0];
	//移除根結點
	preTree.RemoveAt(0);
	
	//建立結點存儲目前值，并指向左右子樹
	TreeNode treeNode=new TreeNode(rootTree);
	
	//左右子樹
	List<int> midLeft=null;
	List<int> tempMid=new AarrayList<int>();//中序周遊左右子樹
	List<int> preLeft=null;
	List<int> tempPre=new AarrayList<int>();//前序周遊左右子樹
	bool isTree=false;
	
	foreach(var item in midTree)
	{
		tempMid.Add(item);
		tempPre.Add(preTree[i++]);
		if(item==rootTree)
		{
			
			//确認是一棵二叉樹
			isTree=true;
			//左子樹的中序周遊
			midLeft=tempMid;
			//中序周遊移除根結點
			midTree.RemoveAt(item);
			//建立臨時結點，存儲右子樹
			tempMid=new List<int>();
			//左子樹的前序周遊
			preLeft=tempPre;
			tempPre=new List<int>();
		}	
	}
	if(!isTree)
	{
		Console.WriteLine("不是正确的數");
		return null;
	}
	List<int> midRight=tempMid;
	List<int> preRight=tempPre;
	
	//遞歸左右子樹
	treeNode.left=Tree(preLeft,midLeft);
	treeNode.right=Tree(preRight,midRight);
		
		
}
           

二、二叉樹操作

二叉樹結構：

public class TreeNode
{
	public int val;
	public TreeNode left;
	public TreeNode right;
	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<int> 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);
			}			
		}
		
	}
}
           

感謝參考部落格：

https://www.cnblogs.com/zhao123/p/11138608.html