Faits :
A.
A.a. A._ a été nommé en qualité de préposé à l'Office X._ par le Conseil d'Etat du canton du Valais. A la suite de la liquidation d'une succession dont il avait été chargé, le prénommé a fait l'objet d'une procédure pénale ainsi que d'une procédure disciplinaire ouverte par l'autorité de nomination. Le 20 juin 2012, le Conseil d'Etat a décidé de diminuer de moitié le traitement de l'intéressé pour une période de trois mois à compter du 1 er juillet 2012. A._ a été acquitté par la Cour des affaires pénales du Tribunal pénal fédéral par jugement du 29 janvier 2013, confirmé par le Tribunal fédéral par arrêt du 22 juillet 2013 (6B_235/2013).
Le recours formé par A._ contre la décision du gouvernement cantonal du 20 juin 2012 a été rejeté par le Tribunal cantonal du Valais (jugement du 24 mai 2013). Saisi d'un recours du prénommé, le Tribunal fédéral a annulé jugement cantonal ainsi que la décision du Conseil d'Etat du 20 juin 2012. Il a condamné le canton du Valais à verser une indemnité de dépens au recourant et a renvoyé la cause à la juridiction précédente pour qu'elle statue à nouveau sur la répartition des frais et dépens de la procédure cantonale (arrêt 8D_3/2013 du 22 juillet 2014, publié aux <ref-ruling>).
A.b. Par jugement du 22 août 2014, le Tribunal cantonal du Valais a notamment alloué à A._ une indemnité de dépens de 2'200 fr. à la charge du canton, précisant dans ses motifs que cette indemnité couvrait ses frais de représentation durant la procédure de recours de droit administratif, l'indemnisation en première instance n'étant dans son principe pas prévue par la loi cantonale sur la procédure et la juridiction administratives (LPJA; RS/VS 172.6).
Par décision du 21 janvier 2015, le Conseil d'Etat a constaté que l'arrêt du Tribunal fédéral du 22 juillet 2014 (<ref-ruling>, ci-dessus mentionné) avait éteint la procédure disciplinaire ouverte à l'encontre de A._ et il a statué sur le traitement auquel celui-ci avait droit depuis le 1 er janvier 2010.
B.
Par acte du 25 février 2015, le prénommé a recouru devant le Tribunal cantonal en concluant à l'annulation de la décision du 21 janvier 2015 et au renvoi de la cause au Conseil d'Etat. Il a fait valoir notamment que, depuis le 25 août 2014, il avait eu des discussions avec les services d'une conseillère d'Etat et cette dernière en personne, au sujet de son retour dans ses anciennes fonctions de préposé dans un office, discussions au cours desquelles il avait été question non seulement de son traitement, mais aussi des frais d'avocat qu'il avait encourus dans les procédures engagées à son endroit.
Préalablement, le 20 février 2015, A._ avait saisi la conseillère d'Etat précitée d'une requête tendant en particulier à ce que le gouvernement cantonal lui accorde une indemnisation pour les frais d'avocat susmentionnés. Au vu de la réponse de la conseillère d'Etat, du 2 mars 2015, selon laquelle sa requête faisait l'objet d'un examen et le Conseil d'Etat statuerait sur les frais d'avocat en cause, l'intéressé a proposé la suspension de la procédure. Consulté par le Tribunal cantonal, le Conseil d'Etat a indiqué, le 13 juillet 2015, qu'il entendait laisser la cour cantonale trancher la question des frais d'avocat. Dans sa détermination du 18 novembre 2015 sur le recours de A._, le gouvernement cantonal a indiqué que sa décision du 21 janvier 2015 comportait la renonciation à attribuer à l'intéressé une indemnité pour ses frais de défense.
Par jugement du 18 décembre 2015, la cour cantonale a rejeté le recours.
C.
A._ interjette un recours en matière de droit public et un recours constitutionnel subsidiaire en concluant à la réforme du jugement attaqué en ce sens que la décision du Conseil d'Etat du 21 janvier 2015 est annulée et l'Etat du Valais condamné à lui payer une indemnité de 19'989 fr. 75 au titre des frais de défense qu'il a supportés et qui n'ont pas été couverts par les dépens alloués en procédure fédérale. Subsidiairement, il demande l'annulation du jugement attaqué et le renvoi de la cause à la cour cantonale pour nouvelle décision.
Le Conseil d'Etat conclut à l'irrecevabilité du recours en matière de droit public et, en tout état de cause, au rejet des recours. La cour cantonale a renoncé à se déterminer.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF). Il contrôle donc librement la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 133).
1.1. Le recourant critique le jugement entrepris en tant qu'il confirme une décision fixant son traitement de fonctionnaire sans lui octroyer une indemnité pour des frais d'avocat qu'il a supportés dans le cadre des procédures administratives et pénales dont le sort a justifié le réajustement de ce traitement. Selon la jurisprudence, la décision accessoire sur les frais judiciaires, les dépens ou une amende procédurale doit être qualifiée de la même manière que la décision principale à laquelle elle se rattache (<ref-ruling> consid. 1.2 p. 331; <ref-ruling> consid. 2.1 p. 647).
1.2. En l'espèce, la prétention litigieuse est en partie l'accessoire de la procédure précédente en matière de rapports de travail de droit public car le recourant demande également le remboursement de frais de défense pénale devant le Tribunal pénal fédéral. Il s'agit néanmoins d'un litige concernant un rapport de travail de droit public dès lors qu'il porte sur le remboursement par l'employeur de frais étroitement liés à ce rapport.
Selon l'art. 83 let. g LTF, en matière de rapports de travail de droit public, lorsque, comme en l'espèce, la question de l'égalité des sexes n'est pas en cause, le recours en matière de droit public est irrecevable contre les décisions qui concernent une contestation non pécuniaire. Devant la juridiction précédente, A._ a conclu à l'annulation de la décision du 21 janvier 2015 et au renvoi de la cause au Conseil d'Etat. Il n'en demeure pas moins que le litige porte sur le remboursement de frais, de sorte qu'il s'agit d'une contestation pécuniaire et que, partant, le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. Quant au montant réclamé par le recourant (19'989 fr. 75), il dépasse le seuil requis par l'art. 85 al. 1 let. b LTF.
Pour le surplus, interjeté en temps utile et dans les formes requises contre une décision finale prise par un tribunal cantonal, le recours en matière de droit public respecte les exigences des art. 42, 86 al. 1 let. d, 90 et 100 al. 1 LTF. Il est par conséquent recevable.
En raison de son caractère subsidiaire (art. 113 LTF), le recours constitutionnel, n'est pas recevable.
2.
2.1. La cour cantonale a constaté que la question litigieuse de l'indemnisation des frais d'avocat avait été abordée dans les pourparlers préalables à la décision du Conseil d'Etat du 21 janvier 2015 et que les écritures déposés devant elle par le gouvernement cantonal expliquaient clairement «pourquoi cette autorité refuse de se plier aux exigences que le recourant formule à cet égard». En outre, la juridiction précédente a retenu que «sur les points de droit à examiner dans ce contexte, le pouvoir d'examen du Tribunal est assez large pour l'habiliter à statuer de manière à garantir à la fois les intérêts légitimes de A._ et une correcte application de la loi» et d'écarter, dès lors, toute violation du droit d'être entendu. Les juges cantonaux se sont ensuite limités à examiner si l'intéressé pouvait se prévaloir du principe de la bonne foi, en raison de prétendues assurances qu'il aurait reçues au sujet de la prise en charge des frais querellés et ils ont répondu à cette question par la négative.
2.2. Le recourant invoque notamment une violation de son droit d'être entendu garanti à l'art. 29 al. 2 Cst., en tant que la cour cantonale n'a pas motivé le rejet de son grief selon lequel le Conseil d'Etat avait commis un déni de justice formel en ne statuant pas, dans la décision litigieuse du 21 janvier 2015, sur la question de l'indemnisation de ses frais.
2.3. Le droit d'être entendu, tel qu'il est garanti à l'art. 29 al. 2 Cst., confère à toute personne le droit d'exiger, en principe, qu'un jugement ou une décision défavorable à sa cause soit motivé. Cette garantie tend à donner à la personne touchée les moyens d'apprécier la portée du prononcé et de le contester efficacement, s'il y a lieu, devant une instance supérieure. Elle tend aussi à éviter que l'autorité ne se laisse guider par des considérations subjectives ou dépourvues de pertinence; elle contribue, par là, à prévenir une décision arbitraire. L'objet et la précision des indications à fournir dépendent de la nature de l'affaire et des circonstances particulières du cas (<ref-ruling> consid. 3.3 p. 445; <ref-ruling> consid. 4.3 p. 540 et les références). L'autorité peut se limiter à l'examen des questions décisives pour l'issue du litige; il suffit que le justiciable puisse apprécier correctement la portée de la décision et l'attaquer à bon escient (<ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236 et les arrêts cités).
2.4. En l'occurrence, il n'est pas possible, à la lecture du jugement entrepris, de savoir si la cour cantonale a retenu que le Conseil d'Etat avait statué de manière implicite sur la prétention litigieuse et, le cas échéant, on ignore les motifs pour lesquels cette décision serait fondée, ou si, au contraire, les premiers juges ont eux-mêmes statué sur le point querellé. On ne parvient pas non plus à connaître les raisons pour lesquelles la juridiction précédente a écarté le grief de déni de justice formel soulevé par le recourant. Dans ces circonstances, le jugement attaqué ne contient pas les motifs permettant de comprendre pourquoi la cour cantonale a tranché dans le sens retenu (art. 112 al. 1 let. b LTF), de sorte qu'il doit être annulé et la cause renvoyée à ladite cour pour qu'elle statue à nouveau, conformément à l'art. 112 al. 3 LTF.
Cela étant, le recours en matière de droit public se révèle bien fondé et il n'est pas nécessaire d'examiner plus avant les autres griefs soulevés par le recourant.
3.
Les frais judiciaires doivent être mis à la charge du canton du Valais, qui succombe et qui défend un intérêt patrimonial (art. 66 al. 1 et 4 in fine LTF; cf. <ref-ruling> consid. 8.1.4 p. 40). Le canton versera une indemnité de dépens au recourant qui obtient gain de cause (art. 68 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est admis et le jugement de la Cour de droit public du Tribunal cantonal du Valais du 18 décembre 2015 est annulé. La cause est renvoyée à ladite juridiction pour nouvelle décision au sens des considérants.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
Les frais judiciaires, arrêtés à 1'500 fr., sont mis à la charge du canton du Valais.
4.
Le canton du Valais versera au recourant une indemnité de 2'800 fr. au titre de dépens pour la procédure fédérale.
5.
Le présent arrêt est communiqué aux parties et à la Cour de droit public du Tribunal cantonal du Valais.
Lucerne, le 17 août 2016
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
Le Greffier : Beauverd