java 二叉树中遇到障碍B无法穿越 写一段代码判断能否在树中找到目标值T
时间: 2023-07-15 16:11:44 浏览: 83
以下是一种基于深度优先搜索(DFS)的解法,它可以在二叉树中找到目标值T,如果在搜索过程中遇到了障碍B,则返回false。
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean findTarget(TreeNode root, int target) {
if (root == null) {
return false;
}
if (root.val == target) {
return true;
}
if (root.val == 'B') {
return false;
}
return findTarget(root.left, target) || findTarget(root.right, target);
}
```
该代码中,我们首先判断根节点是否为空,如果是,则返回false。然后判断根节点的值是否等于目标值T,如果是,则返回true。接着判断根节点的值是否等于障碍B,如果是,则返回false。最后,我们递归地在左右子树中查找目标值T,只要有一个子树中找到了目标值T,就返回true。如果左右子树都没有找到目标值T,则返回false。
需要注意的是,该代码中只能判断目标值T是否存在于树中,而不能返回目标值T所在的节点。如果需要返回目标值T所在的节点,可以将返回值改为TreeNode类型,并在递归查找时记录下目标值T所在的节点。
阅读全文