Leetcode 993 : 二叉树的堂兄弟节点

心已赠人 2022-10-16 06:28 81阅读 0赞

https://leetcode-cn.com/problems/cousins-in-binary-tree/

考察点： 二叉树遍历、二叉树节点深度记录、二叉树当前节点父节点记录

import java.util.LinkedList;
    import java.util.Queue;
    
    public class BinaryTreeIsBrother {
        
    
    
        public static class TreeNode {
        
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode() {
        
            }
    
            TreeNode(int val) {
        
                this.val = val;
            }
    
            TreeNode(int val, TreeNode left, TreeNode right) {
        
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
    
        public static boolean isCousins(TreeNode root, int x, int y) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                boolean xFlag = false;
                TreeNode xRoot = null;
                boolean yFlag = false;
                TreeNode yRoot = null;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    if (node.left != null) {
        
                        queue.offer(node.left);
                        if (node.left.val == x) {
        
                            xFlag = true;
                            xRoot = node;
                        }
                        if (node.left.val == y) {
        
                            yFlag = true;
                            yRoot = node;
                        }
                    }
                    if (node.right != null) {
        
                        queue.offer(node.right);
                        if (node.right.val == x) {
        
                            xFlag = true;
                            xRoot = node;
                        }
                        if (node.right.val == y) {
        
                            yFlag = true;
                            yRoot = node;
                        }
                    }
                    if (xFlag && yFlag && (xRoot.val != yRoot.val)) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
        
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            root.right.left = new TreeNode(6);
            root.right.right = new TreeNode(7);
            System.out.println(isCousins(root, 5, 6));
        }
    
    
    }