• 欢迎光临~

颜色二叉树

开发技术 开发技术 2022-10-20 次浏览
颜色二叉树

一棵节点带颜色的二叉树,每个节点除了有id值,还有一个颜色变量color。每个节点的id值不同。

TreeNode类定义:

class TreeNode{ TreeNode left; TreeNode right; int id; // 每个节点的id值不同。 int color; // 颜色 }

问题:

给定一个节点id值,找到该节点最近的相同颜色的祖宗结点的id,找不到返回-1。

方法定义:

public int findSameColorParent(TreeNode root, int id){ // TODO }
 
    Map<Integer,TreeNode> parent = new HashMap<>();
    Map<Integer,TreeNode> self = new HashMap<>();

    public void dfs(TreeNode root) {
        self.put(root.id,root);
        if (root.left != null) {
            parent.put(root.left.id, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.id, root);
            dfs(root.right);
        }
    }


    public int findSameColorParent(TreeNode root, int id){
        dfs(root);
        TreeNode curTreeNode = self.get(id);
        TreeNode parentTreeNode = parent.get(id);
        while(parentTreeNode!=null){
            if(parentTreeNode.color==curTreeNode.color){
                return parentTreeNode.id;
            }else{
                parentTreeNode = parent.get(parentTreeNode.id);
            }
        }
        return -1;
    }

 

程序员灯塔
转载请注明原文链接:颜色二叉树
喜欢 (0)