这是悦乐书的第374次更新,第401篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第235题(顺位题号是993)。在二叉树中,根节点在深度0处,并且每个深度为k的节点的子节点,他们深度为k + 1

如果二元树的两个节点具有相同的深度但具有不同的父节点,则它们是堂兄弟。

我们给出了具有唯一值的二叉树root,以及树中两个不同节点的值xy

当且仅当对应于值x和y的节点是堂兄弟时,才返回true。例如:

输入:root = [1,2,3,4],x = 4,y = 3

      1
    /   
   2     3
  / 
 4

输出:false


输入:root = [1,2,3,null,4,null,5],x = 5,y = 4

      1
    /   
   2     3
         
     4     5

输出:true


输入:root = [1,2,3,null,4],x = 2,y = 3

      1
    /   
   2     3
     
     4

输出:false

注意

  • 树中的节点数将介于2和100之间。

  • 每个节点都有一个从1到100的唯一整数值。

02 第一种解法

题目的意思是xy在同一层,但是他们的父级节点不一样,也就是xy属于堂兄弟的关系。

使用BFS(广度优先)的算法,通过迭代的方式借助Stack来实现,使用了一个额外的方法,分别求出xy的层级和他们的父级节点,用一个长度为2的数组返回,如果xy的层级相同且父级结点不同,就返回true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins(TreeNode root, int x, int y) {
    int[] arr = getTreeDepth(root, x);
    int[] arr2 = getTreeDepth(root, y);
    if (arr.length < 1 || arr2.length < 1) {
        return false;
    }
    return arr[0] != arr2[0] && arr[1] == arr2[1];
}

public int[] getTreeDepth(TreeNode root, int num) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    int depth = 0;
    while (!stack.isEmpty()) {
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem.left != null) {
                // 当前节点的左子节点值等于要找的数
                if (tem.left.val == num) {
                    return new int[] {tem.val, depth+1};
                }
                stack2.push(tem.left);
            }
            if (tem.right != null) {
                // 当前节点的右子节点值等于要找的数
                if (tem.right.val == num) {
                    return new int[] {tem.val, depth+1};
                }
                stack2.push(tem.right);
            }
        }
        stack = stack2;
        depth++;
    }
    return new int[] {};
}


03 第二种解法

针对第一种解法,我们也可以将判断的方法融合在一起,依旧是借助

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins2(TreeNode root, int x, int y) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        boolean xExist = false, yExist = false;
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            if (tem.val == x) {
                xExist = true;
            }
            if (tem.val == y) {
                yExist = true;
            }
            // x和y不能有同一个父节点
            if (tem.left != null && tem.right != null) {
                if (tem.left.val == x && tem.right.val == y) {
                    return false;
                }
                if (tem.left.val == y && tem.right.val == x) {
                    return false;
                }
            }
            if (tem.left != null) {
                stack2.push(tem.left);
            }
            if (tem.right != null) {
                stack2.push(tem.right);
            }
        }
        stack = stack2;
        if (xExist && yExist) {
            return true;
        }
    }
    return false;
}


04 第三种解法

和第二种解法思路一样,只是将栈换成了队列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins3(TreeNode root, int x, int y) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        boolean xExist = false, yExist = false;
        for (int i=0; i<size; i++) {
            TreeNode tem = queue.poll();
            if (tem.val == x) {
                xExist = true;
            }
            if (tem.val == y) {
                yExist = true;
            }
            // x和y不能有同一个父节点
            if (tem.left != null && tem.right != null) {
                if (tem.left.val == x && tem.right.val == y) {
                    return false;
                }
                if (tem.left.val == y && tem.right.val == x) {
                    return false;
                }
            }
            if (tem.left != null) {
                queue.offer(tem.left);
            }
            if (tem.right != null) {
                queue.offer(tem.right);
            }
        }
        if (xExist && yExist) {
            return true;
        }
    }
    return false;
}


05 第四种解法

借助递归,一个递归方法求深度,一个递归方法找父节点,最后判断深度是否相同且父节点不同。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isCousins4(TreeNode root, int x, int y) {
    return getDepth(root, x, 0) == getDepth(root, y, 0) && 
            findParent(root, x) != findParent(root, y);
}

public int getDepth(TreeNode root, int num, int depth){
    if (root == null) {
        return 0;
    }
    if (root.val == num) {
        return depth;
    }
    int left = getDepth(root.left, num, depth+1);
    int right = getDepth(root.right, num, depth+1);
    return Math.max(left, right);
}

public int findParent(TreeNode root, int num) {
    if (root == null) {
        return 0;
    }
    if (root.left != null && root.left.val == num) {
        return root.val;
    }
    if (root.right != null && root.right.val == num) {
        return root.val;
    }
    int left = findParent(root.left, num);
    int right = findParent(root.right, num);
    return Math.max(left, right);
}


06 第五种解法

我们也可以只是用一次递归方法,借助全局变量来解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

private int depthX;
private int depthY;
private TreeNode parentX;
private TreeNode parentY;

public boolean isCousins5(TreeNode root, int x, int y) {
    helper(root, x, y, 0, null);
    return depthX == depthY && parentX != parentY;
}

public void helper(TreeNode root, int x, int y, int depth, TreeNode parent) {
    if (root == null) {
        return ;
    }
    if (root.val == x) {
        depthX = depth;
        parentX = parent;
    } else if (root.val == y) {
        depthY = depth;
        parentY = parent;
    }
    helper(root.left, x, y, depth+1, root);
    helper(root.right, x, y, depth+1, root);
}


07 第六种解法

我们还可以将第五种解法中找父节点的变量换成int类型,因为节点值唯一,可以直接使用节点值参与判断。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

private int depthX;
private int depthY;
private int parentX;
private int parentY;

public boolean isCousins6(TreeNode root, int x, int y) {
    helper(root, x, y, 0, 0);
    return depthX == depthY && parentX != parentY;
}

public void helper(TreeNode root, int x, int y, int depth, int parent) {
    if (root == null) {
        return ;
    }
    if (root.val == x) {
        depthX = depth;
        parentX = parent;
    } else if (root.val == y) {
        depthY = depth;
        parentY = parent;
    }
    helper(root.left, x, y, depth+1, root.val);
    helper(root.right, x, y, depth+1, root.val);
}


08 小结

算法专题目前已连续日更超过七个月,算法题文章241+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!