树
深度优先搜索
二叉树
题目描述
给你一棵 完整二叉树 的根,这棵树有以下特征:
叶子节点 要么值为 0
要么值为 1
,其中 0
表示 False
,1
表示 True
。
非叶子节点 要么值为 2
要么值为 3
,其中 2
表示逻辑或 OR
,3
表示逻辑与 AND
。
计算 一个节点的值方式如下:
如果节点是个叶子节点,那么节点的 值 为它本身,即 True
或者 False
。
否则,计算 两个孩子的节点值,然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root
的布尔运算值。
完整二叉树 是每个节点有 0
个或者 2
个孩子的二叉树。
叶子节点 是没有孩子的节点。
示例 1:
输入: root = [2,1,3,null,null,0,1]
输出: true
解释: 上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ,所以我们返回 true 。
示例 2:
输入: root = [0]
输出: false
解释: 根节点是叶子节点,且值为 false,所以我们返回 false 。
提示:
树中节点数目在 [1, 1000]
之间。
0 <= Node.val <= 3
每个节点的孩子数为 0
或 2
。
叶子节点的值为 0
或 1
。
非叶子节点的值为 2
或 3
。
解法
方法一:递归
我们可以使用递归的方式来求解本题。
对于当前节点 root
:
如果其左右孩子都为空,说明是叶子节点,此时判断其值是否为 $1$,如果是,则返回 true
,否则返回 false
。
否则,对其左右孩子分别递归求解,得到其左右孩子的值 $l$ 和 $r$。然后根据当前节点值的不同,分别进行如下操作:
如果当前节点值为 $2$,则返回 l or r
。
如果当前节点值为 $3$,则返回 l && r
。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为二叉树节点个数。
Python3 Java C++ Go TypeScript Rust C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 # 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 evaluateTree ( self , root : Optional [ TreeNode ]) -> bool :
def dfs ( root ):
if root . left is None and root . right is None :
return bool ( root . val )
l , r = dfs ( root . left ), dfs ( root . right )
return ( l or r ) if root . val == 2 else ( l and r )
return dfs ( root )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 /**
* 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 evaluateTree ( TreeNode root ) {
return dfs ( root );
}
private boolean dfs ( TreeNode root ) {
if ( root . left == null && root . right == null ) {
return root . val == 1 ;
}
boolean l = dfs ( root . left ), r = dfs ( root . right );
if ( root . val == 2 ) {
return l || r ;
}
return l && r ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
bool evaluateTree ( TreeNode * root ) {
return dfs ( root );
}
bool dfs ( TreeNode * root ) {
if ( ! root -> left && ! root -> right ) return root -> val ;
bool l = dfs ( root -> left ), r = dfs ( root -> right );
if ( root -> val == 2 ) return l || r ;
return l && r ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func evaluateTree ( root * TreeNode ) bool {
var dfs func ( * TreeNode ) bool
dfs = func ( root * TreeNode ) bool {
if root . Left == nil && root . Right == nil {
return root . Val == 1
}
l , r := dfs ( root . Left ), dfs ( root . Right )
if root . Val == 2 {
return l || r
}
return l && r
}
return dfs ( root )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function evaluateTree ( root : TreeNode | null ) : boolean {
const { val , left , right } = root ;
if ( left == null ) {
return val === 1 ;
}
if ( val === 2 ) {
return evaluateTree ( left ) || evaluateTree ( right );
}
return evaluateTree ( left ) && evaluateTree ( right );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: rc :: Rc ;
use std :: cell :: RefCell ;
impl Solution {
fn dfs ( root : & Option < Rc < RefCell < TreeNode >>> ) -> bool {
let root = root . as_ref (). unwrap (). as_ref (). borrow ();
if root . left . is_none () {
return root . val == 1 ;
}
if root . val == 2 {
return Self :: dfs ( & root . left ) || Self :: dfs ( & root . right );
}
Self :: dfs ( & root . left ) && Self :: dfs ( & root . right )
}
pub fn evaluate_tree ( root : Option < Rc < RefCell < TreeNode >>> ) -> bool {
Self :: dfs ( & root )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool evaluateTree ( struct TreeNode * root ) {
if ( ! root -> left ) {
return root -> val == 1 ;
}
if ( root -> val == 2 ) {
return evaluateTree ( root -> left ) || evaluateTree ( root -> right );
}
return evaluateTree ( root -> left ) && evaluateTree ( root -> right );
}
方法二
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13 # 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 evaluateTree ( self , root : Optional [ TreeNode ]) -> bool :
if root . left is None :
return bool ( root . val )
l = self . evaluateTree ( root . left )
r = self . evaluateTree ( root . right )
return l or r if root . val == 2 else l and r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 /**
* 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 evaluateTree ( TreeNode root ) {
if ( root . left == null ) {
return root . val == 1 ;
}
boolean l = evaluateTree ( root . left );
boolean r = evaluateTree ( root . right );
return root . val == 2 ? l || r : l && r ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
bool evaluateTree ( TreeNode * root ) {
if ( ! root -> left ) {
return root -> val ;
}
bool l = evaluateTree ( root -> left );
bool r = evaluateTree ( root -> right );
return root -> val == 2 ? l or r : l and r ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func evaluateTree ( root * TreeNode ) bool {
if root . Left == nil {
return root . Val == 1
}
l , r := evaluateTree ( root . Left ), evaluateTree ( root . Right )
if root . Val == 2 {
return l || r
}
return l && r
}
GitHub