06. 從尾到頭打印鏈表

輸入一個鏈表的頭節(jié)點(diǎn)泡仗，從尾到頭反過來返回每個節(jié)點(diǎn)的值（用數(shù)組返回）。

示例 1：

輸入：head = [1,3,2]
輸出：[2,3,1]

限制：

0 <= 鏈表長度 <= 10000

解決辦法

借助strack棧后進(jìn)先出的原理侵贵，將鏈表節(jié)點(diǎn)依次push入棧，再依次pop出棧即可完成從尾到頭打印鏈表

public class Solution {
    public int[] ReversePrint(ListNode head) {
        Stack<ListNode>st = new Stack<ListNode>();//定義棧名st
        while(head != null){//入棧循環(huán)
            st.Push(head);
            head=head.next;
        }
        var num = st.Count;//計(jì)算出棧中元素的個數(shù)
        int []arr = new int[num];//新的數(shù)組結(jié)構(gòu)
        for(int i=0;i<num;i++)//依次pop出棧
            arr[i] = st.Pop().val;
        return arr;//返回打印出的數(shù)組 完成
    }
    
}

#### 劍指 Offer 07. 重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果缘薛，請重建該二叉樹卡睦。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如蔫骂，給出

前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹
3
/ ? \
9 ? 20
? ? / ? \
? 15 ? 7

限制：

0 <= 節(jié)點(diǎn)個數(shù) <= 5000

解決方法

主要借助了遍歷的思想

public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) 
    {
        if(preorder.Length == 0 || inorder.Length == 0 || preorder.Length != inorder.Length) return null;//進(jìn)行判空
        int preIndex = 0;//聲明前序遍歷中使用的指針
        return BuildTree(preorder, inorder, 0, inorder.Length - 1, ref preIndex);
    }

    public TreeNode BuildTree(int[] preorder, int[] inorder, int inLeft, int inRight, ref int preIndex)//重載遍歷方法么翰，其中inLeft與inRight為中序遍歷數(shù)組中的最左與最右元素的指針
    {
        int val = preorder[preIndex++];//該值為每次遍歷輸出的值
        TreeNode treeNode = new TreeNode(val);

        int L = inLeft;//L值為此時中序遍歷中最左端指針
        while(L < inRight){
            if(inorder[l] == val) break;//當(dāng)最左端指針的值與前序遍歷中當(dāng)前根節(jié)點(diǎn)的值相等時牺汤，則認(rèn)為找到了當(dāng)前中序遍歷中的根節(jié)點(diǎn)
            L++;
        }

        if(L - inLeft > 0) treeNode.left = BuildTree(preorder, inorder, inLeft, L - 1, ref preIndex);//判斷當(dāng)前節(jié)點(diǎn)存在左子樹辽旋。有則遞歸
        if(inRight - L > 0) treeNode.right = BuildTree(preorder, inorder, L + 1, inRight, ref preIndex);//判斷當(dāng)前節(jié)點(diǎn)存在右子樹，有則遞歸

        return treeNode;
    }
}