跳到主要内容

算法刷题-二叉树

144. 二叉树的前序遍历​

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思路​

前序遍历：中左右 使用栈的时候要注意：先放右儿子，再放左儿子，再放中间，这样可以保证出栈的时候：中左右 放自己的时候，需要放一个空指针作为标记

代码​

递归版本

/**
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root,res);
        return res;
    }

    void dfs(TreeNode *root ,vector<int> &res){
        if(root==nullptr) return;
        res.push_back(root->val);
        dfs(root->left,res),dfs(root->right,res);
    }
};

栈版本

/**
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            auto t=st.top();
            st.pop();
            if(t!=nullptr){
                //中左右
                if(t->right) st.push(t->right);
                if(t->left) st.push(t->left);
                st.push(t),st.push(nullptr);
            }else{
                t=st.top();
                st.pop();
                res.push_back(t->val);
            }
        }
        return res;
    }
};

145. 二叉树的后序遍历​

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

思路​

后序遍历：左右中 使用栈遍历的时候，先放自己，在右儿子，在左儿子。这样可以保证出栈的时候顺序为：左右中

代码​

递归版本

/**
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root,res);
        return res;
    }

    void dfs(TreeNode *root,vector<int> &res){
        if(root==nullptr) return;
        dfs(root->left,res),dfs(root->right,res);
        res.push_back(root->val);
    }
};

栈版本：

/**
 * 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:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            auto t=st.top();
            st.pop();
            if(t==nullptr){
                t=st.top();
                st.pop();
                res.push_back(t->val);
            }else{
                //左右中
                st.push(t),st.push(nullptr);
                if(t->right)st.push(t->right);
                if(t->left)st.push(t->left);
            }
        }
        return res;
    }
};

94. 二叉树的中序遍历​

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

思路​

中序遍历：左中右 在使用栈遍历的时候，先让右儿子，再放左儿子，再放中间，这样可以保证出来的时候顺序为：左中右 放自己的时候，再放一个空指针作为标记，下次遍历到空指针的时候，下一个就是自己

代码​

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        dfs(root,res);
        return res;
    }
    void dfs(TreeNode *root,vector<int> &res){
        if(root==nullptr) return;
        dfs(root->left,res);
        res.push_back(root->val);
        dfs(root->right,res);
    }
};

栈版本

/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if(root!=nullptr) st.push(root);
        while(!st.empty()){
            auto t=st.top();
            if(t!=nullptr){
                st.pop();
                if(t->right) st.push(t->right);
                st.push(t);
                st.push(nullptr);
                if(t->left) st.push(t->left);
            }else{
                st.pop();
                t=st.top();
                st.pop();
                res.push_back(t->val);
            }
        }
        return res;
    }
};

102. 二叉树的层序遍历​

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路​

使用队列进行广度优先搜索，每次需要push_back的vector的大小应该根据上一次还剩余的队列的长度进行计算。

代码​

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(q.size()){
            int sz=q.size();
            vector<int> cur;
            while(sz--){
                auto t=q.front();
                q.pop();
                cur.push_back(t->val);
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            res.push_back(cur);
        }
        return res;

    }
};

107. 二叉树的层序遍历 II​

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路​

在上一题的基础上，只需要将从上往下遍历的结果reverse一下即可。

代码​

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(root!=nullptr) q.push(root);
        while(q.size()){
            int sz=q.size();
            vector<int> cur;
            while(sz--){
                auto t=q.front();
                q.pop();
                cur.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            res.push_back(cur);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

199. 二叉树的右视图​

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路​

广度优先搜索，答案就是二叉树的最右侧的节点 遍历每层的时候，就把len(queue)-1的节点加入到结果即可。

代码​

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        if not root:
            return res
        queue=collections.deque([root])
        while queue:
            sz=len(queue)
            for i in range(sz):
                node =queue.popleft()
                if i == sz-1:
                    res.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

637. 二叉树的层平均值​

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

思路​

和上一题一样，本次到len(queue)-1的最后一个节点的时候，把计算的结果加入到结果中

代码​

# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res = []
        if not root:
            return res
        q = collections.deque([root])
        while q:
            sz = len(q)
            sum = 0
            for i in range(sz):
                t = q.popleft()
                sum += t.val
                if t.left:
                    q.append(t.left)
                if t.right:
                    q.append(t.right)
                if i == sz - 1:
                    res.append(sum / sz)
        return  res

429. N 叉树的层序遍历​

给定一个 N 叉树，返回其节点值的_层序遍历_。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

思路​

广度优先搜索：每次不再区分左子树和右子树，直接遍历所有的children，加入队列

代码​

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        res = []
        if not root:
            return res
        q = collections.deque([root])
        while q:
            sz = len(q)
            cur = []
            for i in range(sz):
                t = q.popleft()
                cur.append(t.val)
                for child in t.children:
                    q.append(child)
            res.append(cur)
        return res

515. 在每个树行中找最大值​

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

思路​

广度优先搜索，每层开一个比−231-2^{31}还 小的数，然后不断更新这个为最大值

代码​

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        q = collections.deque([root])
        while q:
            sz = len(q)
            mx = -10000000000
            for _ in range(sz):
                t = q.popleft()
                mx = max(mx, t.val)
                if t.left:
                    q.append(t.left)
                if t.right:
                    q.append(t.right)
                if _ == sz - 1:
                    res.append(mx)
        return res

116. 填充每个节点的下一个右侧节点指针​

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

思路​

把当前层的节点都弹出放入列表中，然后遍历列表，使得每个元素的next指向下一个 注意最后一个要指向空：None

代码​

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        queue = collections.deque([root])
        while queue:
            sz = len(queue)
            ls = []
            for _ in range(sz):
                node = queue.popleft()
                ls.append(node)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            for i in range(len(ls) - 1):
                ls[i].next = ls[i + 1]
            ls[len(ls) - 1].next = None
        return root

117. 填充每个节点的下一个右侧节点指针 II​

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

思路​

根上一题的做法一模一样，代码不用变

代码​

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        q = collections.deque([root])
        while q:
            sz = len(q)
            ls = []
            for _ in range(sz):
                node = q.popleft()
                ls.append(node)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                for i in range(len(ls)-1):
                    ls[i].next = ls[i+1]
                ls[len(ls) - 1].next = None
        return root

104. 二叉树的最大深度​

给定一个二叉树 root ，返回其最大深度。

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

思路​

递归： 如果左子树不为空，那么就进入左子树，如果右子树不为空，那么就进入右子树 当前点的深度 为 左/右 递归得到的结果+1

代码​

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        l = self.maxDepth(root.left)
        r = self.maxDepth(root.right)
        return max(l, r) + 1

111. 二叉树的最小深度​

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

思路​

广度优先搜索，当那一层没有左子树 并且没有右子树的时候，直接返回答案，此时就是最小的深度

代码​

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = collections.deque([(root, 1)])
        while queue:
            node, depth = queue.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))
        return 0

226. 翻转二叉树​

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

思路​

翻转二叉树的问题。首先判断根节点是否为空，如果为空则直接返回。然后交换根节点的左右子节点，再递归地对左右子树进行翻转操作。最后返回根节点。

代码​

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

101. 对称二叉树​

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

思路​

首先判断根节点1是否为空，如果为空则直接返回True。然后调用dfs函数来判断左右子树是否对称。在dfs函数中，

  1. 首先判断左右子节点是否为空，如果一个为空而另一个不为空，则返回False。
  2. 然后判断左右子节点的值是否相等，如果不相等则返回False。
  3. 接着递归地对左子树的左节点和右子树的右节点进行判断，同时对左子树的右节点和右子树的左节点进行判断。
  4. 如果两个递归返回都是true，说明她们对称

代码​

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        return self.dfs(root.left,root.right)

    def dfs(self, left: TreeNode, right: TreeNode):
        if left is None and right:
            return False
        elif left and right is None:
            return False
        elif left is None and right is None:
            return True
        elif left.val != right.val:
            return False

        outside = self.dfs(left.left, right.right)
        inside = self.dfs(left.right, right.left)
        return outside and inside

222. 完全二叉树的节点个数​

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

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

思路​

初始化队列并将根节点加入队列中。然后进入循环，每次循环开始前先记录当前队列的长度，表示当前层的节点个数。然后通过循环遍历当前层的节点，每遍历一个节点，计数器cnt加1。同时，如果当前节点有左子节点，则将左子节点加入队列；如果当前节点有右子节点，则将右子节点加入队列。最后返回计数器cnt的值，即为二叉树的节点个数。

代码​

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = collections.deque([root])
        cnt = 0
        while queue:
            sz = len(queue)
            for i in range(sz):
                node = queue.popleft()
                cnt += 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return cnt

110. 平衡二叉树​

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

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

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

思路​

平衡二叉树是指对于任意一个节点，它的左子树和右子树的高度差不超过1。 这里使用深度优先搜索（DFS）的方法来解决：

  • 首先定义一个辅助函数dfs，它返回当前节点的高度。在dfs函数中，先递归计算左子树的高度，再递归计算右子树的高度。
  • 如果左子树或右子树的高度差超过1，或者左子树或右子树不是平衡二叉树，则返回-1表示不是平衡二叉树。
  • 否则，返回左子树和右子树中较大的高度加1。
  • 最后，在isBalanced函数中，判断根节点的高度是否大于等于0，如果是则返回True，否则返回False。

代码​

# Definition for a binary tree node.
from typing import Optional


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:
        return self.dfs(root) >= 0

    def dfs(self, root: TreeNode) -> int:
        if root is None:
            return 0
        leftHeight = self.dfs(root.left)
        rightHeight = self.dfs(root.right)
        if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return max(leftHeight, rightHeight) + 1

257. 二叉树的所有路径​

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

叶子节点 是指没有子节点的节点。

思路​

使用深度优先搜索（DFS）的方法来解决。

  • 首先定义一个辅助函数dfs，它接收当前节点cur、当前路径path和结果列表result作为参数。
  • 在dfs函数中，先将当前节点的值加入到路径path中。然后判断当前节点是否为叶子节点，如果是，则将路径path转换为字符串，并将其加入到结果列表result中。
  • 接着，分别递归处理当前节点的左子树和右子树，注意要传入路径path的副本，以免在不同的递归中共享同一个路径。
  • 最后，在binaryTreePaths函数中，判断根节点是否为空，如果是，则直接返回空列表。否则，创建一个空的结果列表res，并调用dfs函数来进行深度优先搜索。最后返回结果列表res即可。

代码​

# Definition for a binary tree node.
from typing import Optional, List


# 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]:
        if root is None:
            return []
        res = []
        self.dfs(root, [], res)
        return res

    def dfs(self, cur: TreeNode, path: List[int], result: List[str]):
        if cur is None:
            return
        path.append(cur.val)
        if not cur.left and not cur.right:
            result.append('->'.join(map(str, path)))
        if cur.left:
            self.dfs(cur.left, path[:], result)
        if cur.right:
            self.dfs(cur.right, path[:], result)

404. 左叶子之和​

给定二叉树的根节点 root ，返回所有左叶子之和。

思路​

这道题是求二叉树中所有左叶子节点的值的和。使用递归的方法来解决。首先判断根节点是否为空，如果是，则直接返回0。然后定义一个变量sum来记录左叶子节点的值的和，初始值为0。接着判断根节点的左子节点是否存在，并且左子节点的左子节点和右子节点都不存在，如果满足条件，则将左子节点的值加到sum中。然后递归调用sumOfLeftLeaves函数来计算左子树中左叶子节点的值的和，并将结果加到sum中。再递归调用sumOfLeftLeaves函数来计算右子树中左叶子节点的值的和，并将结果加到sum中。最后返回sum即可。

代码​

from typing import Optional


# 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 root is None:
            return 0
        sum = 0
        if root.left and root.left.left is None and root.left.right is None:
            sum += root.left.val
        return sum + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)


513. 找树左下角的值​

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。

思路​

这道题是要找出二叉树中最底层最左边的节点的值。使用广度优先搜索（BFS）的方法来解决。

  • 首先创建一个队列queue，并将根节点root加入到队列中。同时初始化一个变量res来记录最底层最左边节点的值，初始值为根节点的值root.val。
  • 然后进行循环，直到队列为空。在每一轮循环中，先获取当前队列的大小sz，表示当前层的节点个数。然后通过循环从队列中取出sz个节点进行处理。在处理节点的过程中，如果当前节点是当前层的第一个节点i==0，则更新res为当前节点的值。
  • 接着判断当前节点是否有左子节点和右子节点，如果有，则将它们加入到队列中。
  • 最后返回res即可。

代码​

# Definition for a binary tree node.
import collections
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = collections.deque([root])
        res = root.val
        while queue:
            sz = len(queue)
            for i in range(sz):
                node = queue.popleft()
                if i == 0:
                    res = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

112. 路径总和​

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

思路​

这道题是判断二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值的和等于给定的目标和targetSum。使用广度优先搜索（BFS）的方法来解决。

  • 首先判断根节点是否为空，如果为空，则直接返回False。然后创建两个队列node_queue和val_queue，分别用来存储节点和节点值。将根节点root和根节点的值root.val分别加入到队列中。
  • 接下来进行循环，直到队列为空。在每一轮循环中，从队列中取出一个节点node和对应的节点值val。判断当前节点是否为叶子节点（即没有左子节点和右子节点），如果是，则判断路径上的节点值之和是否等于目标和targetSum，如果相等，则返回True。如果当前节点有左子节点，则将左子节点和路径上节点值之和加入到队列中。如果当前节点有右子节点，则将右子节点和路径上节点值之和加入到队列中。
  • 最后如果循环结束仍未找到满足条件的路径，则返回False。

代码​

# Definition for a binary tree node.
import collections


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from typing import Optional


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        node_queue = collections.deque([root])
        val_queue = collections.deque([root.val])
        while node_queue:
            node = node_queue.popleft()
            val = val_queue.popleft()
            if not node.left and not node.right: # 叶子
                if targetSum==val:
                    return True
            if node.left:
                node_queue.append(node.left)
                val_queue.append(node.left.val+val)
            if node.right:
                node_queue.append(node.right)
                val_queue.append(node.right.val+val)
        return False

106. 从中序与后序遍历序列构造二叉树​

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路​

中序遍历：左根右 后序遍历：左右根 因此postorder的最后一个就是根节点

深度优先搜索（DFS）

  • 首先定义一个辅助函数dfs，接收两个参数l和r，表示当前子树的中序遍历的起始位置和结束位置。如果l大于r，说明当前子树为空，返回None。
  • 然后从后序遍历的结果中取出最后一个元素作为当前子树的根节点的值val，并创建一个节点root。接着通过字典mp来获取val在中序遍历结果中的索引idx。根据idx将中序遍历结果分为左子树和右子树的部分，分别递归调用dfs函数构建左子树和右子树，并将它们分别赋值给root的左子节点和右子节点。
  • 最后返回root即可。在主函数buildTree中，首先创建一个空字典mp，用来存储中序遍历结果中每个元素的索引。然后通过循环遍历中序遍历结果，将每个元素及其索引存入字典中。接着调用dfs函数，传入中序遍历结果的起始位置0和结束位置len(inorder)-1，返回构建好的二叉树的根节点。

代码​

# Definition for a binary tree node.
from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def dfs(l, r) -> TreeNode:
            if l > r:
                return None
            val = postorder.pop()
            root = TreeNode(val)
            idx = mp[val]
            root.right = dfs(idx + 1, r)
            root.left = dfs(l, idx - 1)
            return root

        mp = {}
        for i in range(len(inorder)):
            mp[inorder[i]] = i
        return dfs(0, len(inorder) - 1)

654. 最大二叉树​

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

思路​

使用深度优先搜索（DFS）

  • 首先定义一个辅助函数dfs，接收两个参数l和r，表示当前子数组的起始位置和结束位置。如果l大于r，说明当前子数组为空，返回None。
  • 然后在当前子数组中找到最大值mx及其索引idx。遍历子数组，如果找到比当前最大值mx更大的元素，则更新最大值mx和索引idx。创建一个节点root，值为最大值mx。然后根据idx将子数组分为左子数组和右子数组，分别递归调用dfs函数构建左子树和右子树，并将它们分别赋值给root的左子节点和右子节点。
  • 最后返回root即可。在主函数constructMaximumBinaryTree中，调用dfs函数，传入数组的起始位置0和结束位置len(nums)-1，返回构建好的最大二叉树的根节点。

代码​

# Definition for a binary tree node.
from typing import Optional, List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(l, r) -> TreeNode:
            if l > r:
                return None
            mx = nums[l]
            idx = l
            for i in range(l, r + 1):
                if nums[i] > mx:
                    mx = nums[i]
                    idx = i
            root = TreeNode(mx)
            root.left = dfs(l, idx - 1)
            root.right = dfs(idx + 1, r)
            return root

        return dfs(0, len(nums) - 1)

617. 合并二叉树​

给你两棵二叉树： root1 和 root2 。 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。 返回合并后的二叉树。 注意: 合并过程必须从两个树的根节点开始。

思路​

这道题的思路是通过递归的方式合并两个二叉树。 具体步骤如下：

  1. 首先判断两个根节点 root1 和 root2 是否为空，如果其中一个为空，则返回另一个非空的根节点。
  2. 创建一个新的根节点 root，其值为 root1 和 root2 值的和。
  3. 递归调用 mergeTrees 方法，将 root1 的左子树和 root2 的左子树合并，并将结果赋值给 root 的左子树。
  4. 递归调用 mergeTrees 方法，将 root1 的右子树和 root2 的右子树合并，并将结果赋值给 root 的右子树。
  5. 返回合并后的二叉树 root。 通过递归的方式，可以将两个二叉树的节点逐个合并，最终得到合并后的二叉树。

代码​

# Definition for a binary tree node.
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        root = TreeNode(root1.val + root2.val)
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        return root

700. 二叉搜索树中的搜索​

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

思路​

深度优先搜索（DFS）

  1. 首先定义一个内部函数dfs，它接受一个根节点作为参数。在dfs函数中，首先判断当前节点是否为空，如果为空则返回None。
  2. 然后判断当前节点的值与目标值val的大小关系，如果当前节点的值大于val，则递归调用dfs函数搜索左子树；如果当前节点的值小于val，则递归调用dfs函数搜索右子树；如果当前节点的值等于val，则返回当前节点。
  3. 最后，在searchBST函数中调用dfs函数，并返回其结果。

代码​

# Definition for a binary tree node.
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        def dfs(root):
            if not root:
                return None
            if root.val > val:
                return dfs(root.left)
            if root.val < val:
                return dfs(root.right)
            return root
        return dfs(root)

98. 验证二叉搜索树​

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

思路​

深度优先搜索（DFS）。

  1. 首先定义一个内部函数dfs，它接受一个根节点和上界和下界作为参数。在dfs函数中，首先判断当前节点是否为空，如果为空则返回True。然后获取当前节点的值，并与上界和下界进行比较，如果当前节点的值小于等于下界或大于等于上界，则返回False。
  2. 接着递归调用dfs函数判断左子树是否是BST，如果返回False，则直接返回False。再递归调用dfs函数判断右子树是否是BST，如果返回False，则直接返回False。
  3. 最后，如果左右子树都是BST，则返回True。在isValidBST函数中调用dfs函数，并返回其结果。

代码​

# Definition for a binary tree node.
from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root, lower=float('-inf'), upper=float('inf')):
            if not root:
                return True
            val = root.val
            if val <= lower or val >= upper:
                return False
            if not dfs(root.left, lower, val):
                return False
            if not dfs(root.right, val, upper):
                return False
            return True
        return dfs(root)

0%