leetcode刷题 (9.11) 二叉树

1. 翻转二叉树

226

题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2

思路：三种方法：递归（先序or后序）、dfs（栈）、bfs（层序）

笔记：

C++：

1. 递归法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

Python：

1. 递归法

# 先序
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
1
2
3
4
5
6
7
8
9

2. 迭代法：dfs

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        stack = []
        stack.append(root)

        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 迭代法：bfs (层序)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        from collections import deque
        que = deque([root])

        while que:
            for _ in range(len(que)):
                node = que.popleft()
                node.left, node.right = node.right, node.left 
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 对称二叉树

101

题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

思路：因为要比较的不是两个结点，而是两个树（左右子树），所以要用递归遍历

笔记：

C++：

• 递归法
  递归三部曲：

1. 确定递归函数的参数和返回值
   返回：布尔类型
2. 确定终止条件

if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
1
2
3
4

3. 确定单层递归的逻辑

bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;
1
2
3
4

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Python：

1. 递归法

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 迭代法（队列实现）
   

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        from collections import deque
        # 根节点先入队
        que = deque()

        que.append(root.left)
        que.append(root.right)

        while que:
            leftnode = que.popleft()
            rightnode = que.popleft()
            # 左右结点为空，即此时对称
            if not leftnode and not rightnode:
                continue
            # 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if not leftnode or not rightnode or leftnode.val != rightnode.val:
                return False
            que.append(leftnode.left)
            que.append(rightnode.right)
            que.append(leftnode.right)
            que.append(rightnode.left)
        return True

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

3. n叉树的最大深度

559

题目：给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

输入：root = [1,null,3,2,4,null,5,6]
输出：3
1
2

思路：两种方法，要么迭代法（层序遍历），要么递归法

笔记：

C++：

在这里插入代码片
1

Python：

1. 迭代法

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        results = []
        if not root:
            return 0
        from collections import deque
        que = deque([root])

        while que:
            res = []

            for _ in range(len(que)):
                node = que.popleft()
                res.append(node.val)
                if node.children:
                    que.extend(node.children)
            results.append(res)
        return len(results)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 递归法

递归三部曲：

• 确定参数和返回值——int
• 确定终止条件——结点为空
• 确定单层递归逻辑
  二叉树：先求左子树深度——再求右子树深度——取max(左，右) + 1为根节点的最大深度
  多叉树：左右遍历变成一个一个孩子遍历

# 二叉树
class solution:
    def maxdepth(self, root: treenode) -> int:
        if not root:
            return 0
        return 1 + max(self.maxdepth(root.left), self.maxdepth(root.right))
1
2
3
4
5
6

# 多叉树
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        depth = 0

        for i in range(len(root.children)):
            depth = max(depth, self.maxDepth(root.children[i]))
        return depth + 1
1
2
3
4
5
6
7
8
9
10

4. 完全二叉树的节点个数

222

题目：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

输入：root = [1,2,3,4,5,6]
输出：6
1
2

思路：
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

笔记：

C++：

在这里插入代码片
1

Python：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftdepth = 1
        rightdepth = 1

        # 求向左遍历的深度
        while left:
            left = left.left
            leftdepth += 1
        # 求向右遍历的深度
        while right:
            right = right.right
            rightdepth += 1
        # 左右深度相同，是满二叉，可以直接用公式求
        if leftdepth == rightdepth:
            return (2 ** leftdepth) - 1
        # 否则，该结点+左子树找满二叉+右子树找满二叉
        return self.countNodes(root.left) + self.countNodes(root.right) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5. 平衡二叉树

110

题目：给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入：root = [3,9,20,null,null,15,7]
输出：true
1
2

思路：

对二叉树做后序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

要 求高度——用到后序遍历（左右中）
递归三部曲：

1. 参数和返回值——当前节点，以当前节点为根节点的树的高度。
   如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，返回-1 。
2. 终止条件——遇到空节点
3. 单层递归逻辑——其左子树高度和其右子树高度的差值。
   分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。

笔记：
首先，弄清二叉树深度和高度的区别：

一个节点的高度是从这个结点到底（叶节点）来算的
而深度是从根节点到这个结点来算的

所以求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

C++：

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Python：

• 递归返回值：

当节点root 左 / 右子树的高度差 < 2 ：则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1： （ max(left, right) + 1 ）；

当节点root 左 / 右子树的高度差 ≥2 ：则返回 -1 ，代表 此子树不是平衡树 。

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if self.get_height(root) != -1:
            return True
        else:
            return False

    def get_height(self, root: TreeNode) -> int:
        if not root:
            return 0
        # 求左子树的最大高度，中途高度出现-1，最后结果就直接返回-1
        left_height = self.get_height(root.left)
        if left_height == -1:
            return -1
        # 求右子树的最大高度
        right_height = self.get_height(root.right)
        if right_height == -1:
            return -1
        # 判断他们的父节点，平衡不
        if abs(left_height - right_height) > 1:
            return -1
        # 平衡就从底往上，接着求高度
        else:
            return 1 + max(left_height, right_height)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6. 二叉树的所有路径

257

题目：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
1
2

思路：
从根节点到叶子的路径——前序遍历

需要用回溯来记录回退路径

递归三部曲：

1. 终止条件
   对于二叉树的所有路径中的每条路径，当遍历到叶子节点的时候为当前路径的结束。并且将当前路径加入结果集。

2. 单层递归逻辑
   将根节点加入路径，递归左子树，递归右子树。

笔记：

C++：

在这里插入代码片
1

Python：

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        path = ''
        res = []
        self.get_paths(root, path, res)

        return res

    def get_paths(self, root, path, res):
        if not root:
            return
        # 节点值加入当前路径
        path += str(root.val)
        # 如果当前节点是叶子节点，将当前路径加入结果集
        if root.left == None and root.right == None:
            res.append(path)
        # 如果当前节点不是叶子节点，继续遍历左子树和右子树。
        else:
            path += '->'
            self.get_paths(root.left, path, res)
            self.get_paths(root.right, path, res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21