Construct Binary Tree

发表于 | 分类于 | |

105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题目大意

根据前序和中序，构建二叉树。

解题思路

由于前序遍历的规则是：根->左->右，所以前序遍历的第一个元素为根节点，根据这一特性，将中序数组分为左子树和右子树。重复以上操作。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
       var dict = [Int: Int]() //参考leetcode上的最优解决方案，优化
        for (i, n) in inorder.enumerated() {
            dict[n] = i
        }
        func build(preIndex: Int, start: Int, end: Int) -> TreeNode? {
            guard start <= end else { return nil }
            
            let root = TreeNode(preorder[preIndex])
            let index = dict[preorder[preIndex]] ?? 0
            
            if index > start {
                root.left = build(preIndex: preIndex + 1, start: start, end: index - 1)
            }
            if index < end {
                //由于preIndex + 1之后，首元素其实是左子树，所以需要加上当前inorder数组中，左子树的个数，才能将首元素变为右子树。
                root.right = build(preIndex: preIndex + index - start + 1, start: index + 1, end: end)
            }
            
            return root
        }
        
        return build(preIndex: 0, start: 0, end: inorder.count - 1)
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

题目描述

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题目大意

根据后序和中序，构建二叉树

解题思路

与前序和中序构建树的思路差不多。
需要使用后序特性，最后一个数为根节点。将前序数组分为左右两个子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
   func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        var dict = [Int: Int]() //参考leetcode上的最优解决方案，优化
        for (i, n) in inorder.enumerated() {
            dict[n] = i
        }
        func build(postStart: Int, postEnd: Int, inStart: Int, inEnd: Int) -> TreeNode? {
            guard inStart <= inEnd && postStart <= postEnd else { return nil }
            
            let root = TreeNode(postorder[postEnd])
            let index = dict[postorder[postEnd]] ?? 0
            
            if index > inStart {
                root.left = build(postStart: postStart, postEnd: postStart + index - inStart - 1, inStart: inStart, inEnd: index - 1)
            }
            if index < inEnd {
                root.right = build(postStart: postStart + index - inStart, postEnd: postEnd - 1, inStart: index + 1, inEnd: inEnd)
            }
            
            return root
        }
        
        return build(postStart: 0, postEnd: postorder.count - 1, inStart: 0, inEnd: inorder.count - 1)
    }
}
0%