劍指offer_7_重建二叉樹

• 2019 年 10 月 7 日
• 筆記

題目：重建二叉樹

描述：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重新構建該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中不包含重複的數字。例如輸入的前序遍歷序列為｛5，2，1，7，6，9｝和中序遍歷為{1，2，5，6，7，9},則重建出二叉樹並輸出它的頭結點。

思路：利用前序遍歷根節點左右倆側是左右子樹，中序遍歷第一個節點就根節點的特性，將一棵樹細分成很多子樹，從根節點往下構造。

Map<Integer,Integer> map = new HashMap<>();    public TreeNode fill(int[] pre,int[] in) {      for (int i = 0; i < in.length; i++) {          map.put(in[i],i);      }      return reBuild(pre,0,pre.length -1,0);  }      // pre[] 前序遍歷 preL：當前前序遍曆數組的最左側 preR：當前前序遍曆數組的最右側 inL中序遍歷的最左側  public TreeNode reBuild(int[] pre,int preL,int preR,int inL) {       if (preL > preR) {           return null;       }      TreeNode root = new TreeNode(pre[preL]);       // 得到該節點的下標       int inIndex = map.get(root.value);       // 左子樹的大小       int lTreeSize = inIndex - inL;       // 遞歸左邊的子樹       root.left = reBuild(pre,preL + 1,preL + lTreeSize,inL);       // 遞歸右邊的子樹 inL + lTreeSize + 1:當前中序遍曆數組的最左側元素       root.right = reBuild(pre,preL + lTreeSize + 1,preR,inL + lTreeSize + 1);      return root;   }  }    class TreeNode {      TreeNode left;      TreeNode right;      int value;      public TreeNode(int value) {          this.value = value;      }  }

利用前序後續遍歷的特性，重新構建二叉樹。