1600. 王位继承顺序

王位继承顺序

• 难度: medium
• 原始链接: https://leetcode.cn/problems/throne-inheritance
• 标签: 前序遍历

解法一: 前序遍历

go

type ThroneInheritance struct {
  Root  *Node
  Deads map[string]*Node
}

type Node struct {
  Name     string
  IsDead   bool
  Children *[]*Node
}

func Constructor(kingName string) ThroneInheritance {
  root := &Node{
    Name:     kingName,
    Children: &[]*Node{},
  }
  return ThroneInheritance{
    Root: root,
    Deads: map[string]*Node{
      kingName: root,
    },
  }
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
  node := &Node{
    Name:     childName,
    Children: &[]*Node{},
  }
  children := this.Deads[parentName].Children
  *children = append(*children, node)
  this.Deads[childName] = node
}

func (this *ThroneInheritance) Death(name string) {
  this.Deads[name].IsDead = true
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
  ans := []string{}
  var dfs func(root *Node)
  dfs = func(root *Node) {
    if root == nil {
      return
    }
    if !root.IsDead {
      ans = append(ans, root.Name)
    }
    for _, child := range *root.Children {
      dfs(child)
    }
  }
  dfs(this.Root)
  return ans
}

java

class ThroneInheritance {

    private String kingName;

    private Map<String, List<String>> nodes;

    private Set<String> deads;

    public ThroneInheritance(String kingName) {
        this.kingName = kingName;
        nodes = new HashMap<>();
        deads = new HashSet<>();
    }

    public void birth(String parentName, String childName) {
        nodes.merge(parentName, Collections.singletonList(childName), (children, newChildren) -> {
            if (children.size() == 1) {
                children = new ArrayList<>(children);
            }
            children.addAll(newChildren);
            return children;
        });
    }

    public void death(String name) {
        deads.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> ans = new ArrayList<>();
        this.dfs(kingName, ans);
        return ans;
    }

    private void dfs(String nodeName, List<String> ans) {
        if (!deads.contains(nodeName)) {
            ans.add(nodeName);
        }
        List<String> nodeNames = nodes.getOrDefault(nodeName, Collections.emptyList());
        for (String childName : nodeNames) {
            this.dfs(childName, ans);
        }
    }

}