针对求二叉树深度问题,一般有两种解法:BFS(广度优先搜索)和DFS(深度优先搜索)。
1.BFS:用队列存储每一层的结点。实现广度搜索。
2.DFS:用了递归思想。对于本题情况较多,较难理解。
JAVA
/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public boolean isCousins(TreeNode root, int x, int y) { Deque<TreeNode> deque = new ArrayDeque<>(); deque.addLast(root); while(!deque.isEmpty()){ int size = deque.size(); boolean xexist = false; boolean yexist = false; for(int i = 0; i < size; i++){ TreeNode temp = deque.removeFirst(); if(temp.val == x) xexist = true; if(temp.val == y) yexist = true; if(temp.left != null && temp.right != null){ if(temp.left.val == x && temp.right.val == y) return false; if(temp.left.val == y && temp.right.val == x) return false; } if(temp.left != null) deque.addLast(temp.left); if(temp.right != null) deque.addLast(temp.right); } if(xexist && yexist) return true; } return false; } }
class Solution { public boolean isCousins(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); } }
Python3
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isCousins(self, root: TreeNode, x: int, y: int) -> bool: queue = [] queue.append(root) while queue: n = len(queue) xexist = False yexist = False for i in range(n): node = queue.pop(0) if node.val == x: xexist = True if node.val == y: yexist = True if node.left and node.right: if node.left.val == x and node.right.val == y: return False if node.left.val == y and node.right.val == x: return False if node.left: queue.append(node.left) if node.right: queue.append(node.right) if xexist and yexist: return True return False
class Solution: def isCousins(self, root: TreeNode, x: int, y: int) -> bool: return (self.getDepth(root, x, 0) == self.getDepth(root, y, 0)) and (self.findParent(root, x) != self.findParent(root, y)) def getDepth(self, root, num, depth): if root == None: return 0 if root.val == num: return depth left = self.getDepth(root.left, num, depth+1) right = self.getDepth(root.right, num, depth+1) return max(left, right) def findParent(self, root, num): if root == None: return 0 if root.left != None and root.left.val == num: return root.val if root.right != None and root.right.val == num: return root.val left = self.findParent(root.left, num) right = self.findParent(root.right, num) return max(left, right)