Swift.树中两个节点的最低公共祖先

题目描述：求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。

import Foundation

public class MyTreeNode {
    public var val: Int
    public var children: [MyTreeNode]?
    public init(_ val: Int) {
        self.val = val
        self.children = nil
    }
}

class For50Solution {
    func commonTreeNode(_ root: MyTreeNode,_ a: MyTreeNode,_ b: MyTreeNode) -> MyTreeNode? {

        var list1 = [MyTreeNode]()
        var list2 = [MyTreeNode]()
        getNodePath(root, a, &list1)
        getNodePath(root, b, &list2)

        return getLastCommonNode(list1, list2)
    }
    
    func getNodePath(_ root: MyTreeNode?,_ p: MyTreeNode,_ list: inout [MyTreeNode]) {
        
        if root!.val == p.val {
            return
        }
        
        list.append(root!)
        
        let arr = root!.children
        if arr != nil {
            for node in arr! {
                if node.val == p.val {
                    list.append(node)
                    break
                }
                
                getNodePath(node, p, &list)
            }
        }
        
        if list.last?.val != p.val {
            list.removeLast()
        }
    }
    
    func getLastCommonNode(_ p1: [MyTreeNode],_ p2: [MyTreeNode]) -> MyTreeNode? {
        
        var temp: MyTreeNode? = nil
        var index = 1
        
        while index < p1.count {
            if p1[index].val == p2[index].val {
                temp = p1[index]
                break
            }
            index += 1
        }
        
        return temp
    }
}

算法思想：假设是二叉树做的。还要优化。

github地址：https://github.com/cubegao/LeetCode