Okii's blog

仅作为记录自己的学习过程

0%

Leetcode 二叉树属性篇

发表于 分类于
本文字数： 4.7k 阅读时长 ≈ 9 分钟

Leetcode刷题记录——二叉树属性篇

Leetcode101 对称二叉树

递归三部曲

1、确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。

返回值自然是bool类型。

2、确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

  • 左节点为空，右节点不为空，不对称，return false
  • 左不为空，右为空，不对称 return false
  • 左右都为空，对称，return true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

  • 左右都不为空，比较节点数值，不相同就return false

3、确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

  • 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
  • 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
  • 如果左右都对称就返回true ，有一侧不对称就返回false 。

Python代码如下：

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:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.compare(root.left, root.right)
    def compare(self, left, right):
        if left == None and right != None: 
            return False
        elif left != None and right == None: 
            return False
        elif left == None and right == None: 
            return True
        elif left.val != right.val: 
            return False
        outside = self.compare(left.left, right.right)
        inside = self.compare(left.right, right.left)
        isSame = outside and inside
        return isSame

Leetcode110 平衡二叉树

求高度(到叶子节点的距离) 用后序遍历

求深度(到根节点的距离) 用前序遍历

递归三部曲：

1、明确递归函数的参数和返回值

参数：当前传入节点 返回值：以当前传入节点为根的树的高度

如果，某个节点为根的二叉树已经不是平衡二叉树，那么返回高度就没有必要了，可以返回-1

2、明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

3、明确单层递归的逻辑

分别求其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        if self.get_height(root) == -1:
            return False
        else:
            return True
    def get_height(self, root):
        if not root:
            return 0
        left = self.get_height(root.left)
        right = self.get_height(root.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

Leetcode257 二叉树的所有路径

依旧是递归三部曲：

1、递归函数参数以及返回值

传入根节点，记录每一条路径的path，和存放最终结果的res

2、确定递归的终止条件

那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

3、确定单层递归逻辑

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。

path.append(cur.val)

然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。

此时还没完，递归完，要做回溯，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点

我们知道，回溯和递归是一一对应的，有一个递归，就要有一个回溯，所以回溯要和递归永远在一起

Python代码如下：

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
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        path = []
        if not root:
            return res
        self.traversal(root, path, res)
        return res
    def traversal(self, cur, path, result):
        path.append(cur.val)
        # 说明到达了叶子节点
        if not cur.left and not cur.right:
            # path数组里元素是int, 不能直接join, 要转换str
            str_path = '->'.join(map(str,path))
            result.append(str_path)
            return
        if cur.left:
            self.traversal(cur.left, path, result)
            path.pop()
        if cur.right:
            self.traversal(cur.right, path, result)
            path.pop()

Leetcode404 左叶子之和

依旧是递归三部曲：

1、确定递归函数的参数和返回值

判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和

2、确定终止条件

如果遍历到空节点，那么return 0

3、确定单层递归逻辑

当遇到左叶子节点的时候，记录数值；然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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 sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left_num = self.sumOfLeftLeaves(root.left)
        if root.left and not root.left.left and not root.left.right:
            left_num = root.left.val
        right_num = self.sumOfLeftLeaves(root.right)
        sum = left_num + right_num
        return sum

Leetcode112 路径总和

还是递归三部曲，一直总结加强记忆：

1、确定递归函数的参数和返回值

参数：需要当前子树的根节点和一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和

递归函数什么时候需要或者不需要返回值：

  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。(本题的情况)

2、确定终止条件

如果每次递归累加val，代码处理起来比较麻烦，可以考虑每次递归时，减去当前的val

如果最后targetSum == 0，同时到了叶子节点的话，说明找到了目标和。

如果遍历到了叶子节点，targetSum不为0，就是没找到。

3、确定单层递归的逻辑

因为目前很多题都是遍历到叶子节点，tarversal一开始没有判断空指针

所以在进入递归前要判断其是否是空指针

递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回

而且这道题要注意递归完之后的回溯，减掉的val要再加回去

Python代码如下：

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
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.tarversal(root, targetSum-root.val)

    def tarversal(self, root, targetSum):
        if not root.left and not root.right and targetSum == 0:
            return True
        if not root.left and not root.right and targetSum != 0:
            return False
        if root.left:
            targetSum -= root.left.val
            if self.tarversal(root.left, targetSum):
                return True
            targetSum += root.left.val
        if root.right:
            targetSum -= root.right.val
            if self.tarversal(root.right, targetSum):
                return True
            targetSum += root.right.val
        return False