LeetCode題解之重建二叉樹
前言
今天繼續(xù)二叉樹相關(guān)的算法題
題目
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
- 3
- / \
- 9 20
- / \
- 15 7
題解
上周說過 前序遍歷和后序遍歷，其實(shí)這種前序、中序、后序都是相對于中間節(jié)點(diǎn)的處理順序。
比如先序遍歷的順序就應(yīng)該是：
[ 根節(jié)點(diǎn) | 左子樹 | 右子樹 ]
同理，中序遍歷的順序就是：
[ 左子樹 | 根節(jié)點(diǎn) | 右子樹 ]
所以前序遍歷的第一個元素肯定就是 根節(jié)點(diǎn)。
然后，我們就能在 中序遍歷找到根節(jié)點(diǎn)，并正確把中序遍歷區(qū)分為三部分，也就是左子樹中序、根節(jié)點(diǎn)、右子樹中序。
舉個例子:
如果只有三個元素，那么到這里就能結(jié)束了，因?yàn)闃湟呀?jīng)能畫出來了。
比如前序是【3，9，20】，中序是【9，3，20】
我們根據(jù)中序知道了根節(jié)點(diǎn)3，然后在中序中就能區(qū)分出左子樹節(jié)點(diǎn)9，根節(jié)點(diǎn)3，右子樹節(jié)點(diǎn)20。
現(xiàn)在我們擴(kuò)散開，如果不止3個節(jié)點(diǎn)呢?
舉例2:
如果是5個元素，比如前序是[3,9,20,15,7]，中序是[9,3,15,20,7]
經(jīng)過第一次分割，我們把中序分成了左子樹9，根節(jié)點(diǎn)3，右子樹【15，20，7】
這時候，右子樹該怎么分呢?跟節(jié)點(diǎn)是什么呢?又不知道了。
所以這時候要再聯(lián)系到前序遍歷，根據(jù)我們所知道的左子樹節(jié)點(diǎn)，得出前序中右子樹應(yīng)該為【20，15，7】，所以右子樹的根節(jié)點(diǎn)為20。
總之，就是前序和中序互相幫助，最終通過遞歸完成我們樹的構(gòu)建。
解法1
解法1就是依靠遞歸。
遞歸的過程就是找出每個父節(jié)點(diǎn)的左子樹節(jié)點(diǎn)和右子樹節(jié)點(diǎn)，一共三個值。
而最終的取值都是從前序列表中取值，其實(shí)就是取每個小樹的父節(jié)點(diǎn)。
而中序遍歷數(shù)組的作用就是找到 每次父節(jié)點(diǎn)在中序遍歷數(shù)組中的位置。
得出如下算法。
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- int[] preorder;
- HashMap<Integer, Integer> dic = new HashMap<>();
- public TreeNode buildTree(int[] preorder, int[] inorder) {
- this.preorder = preorder;
- for(int i = 0; i < inorder.length; i++)
- dic.put(inorder[i], i);
- return recur(0, 0, inorder.length - 1);
- }
- TreeNode recur(int root, int left, int right) {
- if(left > right) return null;
- //根節(jié)點(diǎn)
- TreeNode node = new TreeNode(preorder[root]);
- //分割點(diǎn)
- int i = dic.get(preorder[root]);
- node.left = recur(root + 1, left, i - 1);
- node.right = recur(root + i - left + 1, i + 1, right);
- return node;
- }
- }
其中每次取右子樹的根節(jié)點(diǎn)需要注意：
左子樹的節(jié)點(diǎn)數(shù)為i-left。
所以在前序遍歷數(shù)組中，左子樹的節(jié)點(diǎn)+根節(jié)點(diǎn)位置，就是左子樹的最后一個節(jié)點(diǎn)位置，也就是root+i-left。
最后得出右子樹的根節(jié)點(diǎn)為：root + i - left + 1
而遞歸的結(jié)束條件就是，左右子樹節(jié)點(diǎn)相遇，也就是left>right。
時間復(fù)雜度
O(n)，n為樹的節(jié)點(diǎn)數(shù)量。
空間復(fù)雜度
O(N)，用到了HashMap。
解法2
還有一種辦法叫做迭代方法，這個方法挺巧妙的，當(dāng)時也是看了很久的官方解答才想明白的，哈哈。
它的主要思想是理解前序遍歷和中序遍歷的規(guī)則，然后一個個從前序遍歷中取值，并放到合適的位置。
比如以下這個二叉樹：
- 3
- / \
- 9 20
- / / \
- 8 15 7
- / \
- 5 10
- /
- 4
前序遍歷，可以發(fā)現(xiàn)是首先把最左邊的節(jié)點(diǎn)列出來，也就是 3，9，8，5，4
而中序列表是反著來的，從最左邊的下面開始，往上列，如果發(fā)現(xiàn)某個節(jié)點(diǎn)有右子節(jié)點(diǎn)，就開始往右邊列。
比如 4，5，8。這時候發(fā)現(xiàn)8有右子節(jié)點(diǎn)，那么就開始數(shù) 10 ，然后繼續(xù)最左邊往上，9，3。
最后列一下完整的前序和中序：
preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7] inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
總之，前序是從左邊列開始，從上往下排。中序就是從左邊列開始，從下往上排。
看看代碼：
- class Solution {
- public TreeNode buildTree(int[] preorder, int[] inorder) {
- if (preorder == null || preorder.length == 0) {
- return null;
- }
- TreeNode root = new TreeNode(preorder[0]);
- Deque<TreeNode> stack = new LinkedList<TreeNode>();
- stack.push(root);
- int inorderIndex = 0;
- for (int i = 1; i < preorder.length; i++) {
- int preorderVal = preorder[i];
- TreeNode node = stack.peek();
- if (node.val != inorder[inorderIndex]) {
- node.left = new TreeNode(preorderVal);
- stack.push(node.left);
- } else {
- while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
- node = stack.pop();
- inorderIndex++;
- }
- node.right = new TreeNode(preorderVal);
- stack.push(node.right);
- }
- }
- return root;
- }
- }
if語句是為了找到左列最后一個節(jié)點(diǎn)，比如上述例子中的4。
while循環(huán)是當(dāng)發(fā)現(xiàn)有右節(jié)點(diǎn)的時候，要找到右節(jié)點(diǎn)的父節(jié)點(diǎn)，然后添加進(jìn)去。
大家可以手動試試，解法2確實(shí)不太好理解。
至少解法1的遞歸方法是要掌握的。
時間復(fù)雜度
O(n)
空間復(fù)雜度
O(n)
參考
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/
本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。
