【二叉树】根据描述创建二叉树

0x00 题目

给你一个二维整数数组 descriptions
其中 descriptions[i] = [parenti, childi, isLefti] 表示
parenti 是 childi 在 二叉树 中的 父节点
二叉树中各节点的值 互不相同

此外：
如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点
如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点
请你根据 descriptions 的描述来构造二叉树并返回其 根节点

---

0x01 思路

根据所给的数据
创建节点与父节点
再通过一个字典保存对应的
节点与其父节点
最后再判断那个不存在父节点的节点
就是根节点

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func createBinaryTree(_ descriptions: [[Int]]) -> TreeNode? {
    if descriptions.isEmpty { return nil }
    
    // 值对应的节点
    var dic: [Int:TreeNode] = [:]
    // 值对应的父节点
    var per: [Int:TreeNode] = [:]
    // 那些父节点的值
    var arr: [Int] = []
    
    for i in 0..<descriptions.count {
        let t = descriptions[i]
        let p = t[0]
        let c = t[1]
        let isLeft = t[2]
        
        // 取出父节点和子节点
        var pNode = dic[p]
        var cNode = dic[c]
        
        // 不存在就创建
        if pNode == nil {
            pNode = TreeNode(p)
            dic[p] = pNode
            // 添加到数组
            arr.append(p)
        }
        if cNode == nil {
            cNode = TreeNode(c)
            dic[c] = cNode
        }
        
        // 值对应的父节点
        per[c] = pNode
        
        if isLeft == 1 {
            pNode!.left = cNode
        }else{
            pNode!.right = cNode
        }
    }
    
    var root: TreeNode? = nil
    // 从可能的父节点中寻找，没有父节点的，就是根节点
    for i in 0..<arr.count {
        let val = arr[i]
        if per[val] == nil {
            root = dic[val]
        }
    }
    
    return root
}

---

0x03 我的小作品

欢迎体验我的作品之一：小五笔
五笔学习好帮手~
App Store 搜索即可~

---