力扣整理版七：二叉树（待更新）

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。深度为k，有2^k-1个节点的二叉树。

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

二叉搜索树：左<根<右。

平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

-----------------------------

(1) 144 二叉树的前序遍历

(2) 145 二叉树的后序遍历

(3) 94 二叉树的中序遍历

(4) 102 二叉树的层序遍历

(5) 107 二叉树的层序遍历2

(6) 199 二叉树的右视图

(7) 637 二叉树的层平均值

(8) 429 N叉树的层序遍历

(9) 515 在每个树行中找最大值

(10) 116 填充每个节点的下一个右侧节点指针

(11) 117 填充2(18) 404 左叶子之和

(12) 104 二叉树的最大深度

(13) 111 二叉树的最小深度

(14) 226 翻转二叉树

(15) 101 对称二叉树

(16) 222 完全二叉树的节点个数

(17) 257 二叉树的所有路径

(18) 404 左叶子之和

-----------------------------

一、二叉树的递归遍历

1、确定递归函数的参数和返回值；2、确定终止条件；3、确定单层递归的逻辑；

144. 二叉树的前序遍历 - 力扣（LeetCode）

1、前序遍历

 -------------  python  -------------

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)return res

 -------------  c++  -------------

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

2、中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

 -------------  python  -------------

# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res

 -------------  c++  -------------

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右
}

3、后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

-------------  python  -------------

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(node):if node is None:returndfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res

-------------  c++  ------------- 

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 中
}

二、二叉树的迭代遍历

1、前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

-------------  python  -------------

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []stack=[]res=[]while stack or root:if root:res.append(root.val)stack.append(root)root=root.leftelse:tem=stack.pop()root=tem.rightreturn res

-------------  c++  ------------- 

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {if(root==nullptr) return {};stack<TreeNode*> stk;vector<int> res;while(!stk.empty() || root){     //stack不可以转换成bool类型if (root){res.push_back(root->val);stk.push(root);root=root->left;}else{TreeNode* tem=stk.top();stk.pop();root=tem->right;}}return res;}
};

2、中序遍历 

94. 二叉树的中序遍历 - 力扣（LeetCode）

-------------  python  -------------

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""# res = []# def dfs(root):# 	if not root:# 		return# 	# 按照 左-打印-右的方式遍历	# 	dfs(root.left)# 	res.append(root.val)# 	dfs(root.right)# dfs(root)# return res# 上面是递归res = []stack = []while stack or root:# 不断往左子树方向走，每走一次就将当前节点保存到栈中# 这是模拟递归的调用if root:stack.append(root)root = root.left# 当前节点为空，说明左边走到头了，从栈中弹出节点并保存# 然后转向右边节点，继续上面整个过程else:tmp = stack.pop()res.append(tmp.val)root = tmp.rightreturn res

-------------  c++  ------------- 

// 不可写成while(stack)  stack不能转化成bool类型，但是root如果是个指针可以
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>res;stack<TreeNode*>stk;while(root!=nullptr || !stk.empty()){if(root!=nullptr){stk.push(root);root=root->left;}else{root=stk.top();stk.pop();res.push_back(root->val);root=root->right;}}return res;}
};

 3、后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

-------------  python  -------------

class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []res=[]def dfs(root):if not root:returndfs(root.left)dfs(root.right)res.append(root.val)dfs(root)return res

-------------  c++  ------------- 

class Solution {
public:vector<int> res;void dfs(TreeNode* root){if(root==nullptr) return;dfs(root->left);dfs(root->right);res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {if(root==nullptr) return {};dfs(root);return res;}
};

三、二叉树的层序遍历

1、102 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

-------------  python  -------------

# 利用长度法
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []queue = collections.deque([root])result = []while queue:level = []for _ in range(len(queue)):cur = queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level)return result
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []levels = []def traverse(node, level):if not node:returnif len(levels) == level:levels.append([])levels[level].append(node.val)traverse(node.left, level + 1)traverse(node.right, level + 1)traverse(root, 0)return levels

-------------  c++  -------------  

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};
# 递归法
class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

2、107 二叉树的层序遍历2

107. 二叉树的层序遍历 II - 力扣（LeetCode）

题目描述：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

Tips：相对于上一题，把result数组反转。

-------------  python  -------------

class Solution:"""二叉树层序遍历II迭代解法"""# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:if not root:return []queue = collections.deque([root])result = []while queue:level = []for _ in range(len(queue)):cur = queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level)return result[::-1]

-------------  c++  -------------  

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}reverse(result.begin(), result.end()); // 在这里反转一下数组即可return result;}
};

3、199 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

题目描述：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

Tips：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

-------------  python  -------------

class Solution:def rightSideView(self, root: TreeNode) -> List[int]:if not root:return []queue = collections.deque([root])right_view = []while queue:level_size = len(queue)for i in range(level_size):node = queue.popleft()if i == level_size - 1:right_view.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return right_view

-------------  c++  -------------  

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == (size - 1)) result.push_back(node->val); // 将每一层的最后元素放入result数组中if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

4、637 二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode）

题目描述：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

-------------  python  -------------

class Solution:"""二叉树层平均值迭代解法"""# 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: TreeNode) -> List[float]:if not root:return []queue = collections.deque([root])averages = []while queue:size = len(queue)level_sum = 0for i in range(size):node = queue.popleft()level_sum += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)averages.append(level_sum / size)return averages

-------------  c++  -------------  

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<double> result;while (!que.empty()) {int size = que.size();double sum = 0; // 统计每一层的和for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();sum += node->val;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(sum / size); // 将每一层均值放进结果集}return result;}
};

5、429 N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）

题目描述：给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

-------------  python  -------------

lass Solution:def levelOrder(self, root: 'Node') -> List[List[int]]:if not root:return []result = []queue = collections.deque([root])while queue:level_size = len(queue)level = []for _ in range(level_size):node = queue.popleft()level.append(node.val)for child in node.children:queue.append(child)result.append(level)return result

-------------  c++  -------------  

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {Node* node = que.front();que.pop();vec.push_back(node->val);for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列if (node->children[i]) que.push(node->children[i]);}}result.push_back(vec);}return result;}
};

6、515 在每个树行中找最大值

515. 在每个树行中找最大值 - 力扣（LeetCode）

题目描述：在二叉树的每一行中找到最大的值。

-------------  python  -------------

class Solution:def largestValues(self, root: TreeNode) -> List[int]:if not root:return []result = []queue = collections.deque([root])while queue:level_size = len(queue)max_val = float('-inf')for _ in range(level_size):node = queue.popleft()max_val = max(max_val, node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(max_val)return result

-------------  c++  -------------  

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()) {int size = que.size();int maxValue = INT_MIN; // 取每一层的最大值for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();maxValue = node->val > maxValue ? node->val : maxValue;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(maxValue); // 把最大值放进数组}return result;}
};

7、116 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

题目描述：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。

-------------  python  -------------

class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootqueue = collections.deque([root])while queue:level_size = len(queue)prev = Nonefor i in range(level_size):node = queue.popleft()if prev:prev.next = nodeprev = nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

-------------  c++  -------------  

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();// vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

8、117 填充2

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

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

-------------  python  -------------

class Solution:def connect(self, root: 'Node') -> 'Node':if not root:return rootqueue = collections.deque([root])while queue:level_size = len(queue)prev = Nonefor i in range(level_size):node = queue.popleft()if prev:prev.next = nodeprev = nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

-------------  c++  -------------  

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

9、104 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

Tips：使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度。

-------------  python  -------------

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

-------------  c++  -------------  

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return depth;}
};

10、111 二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

题目描述：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

-------------  python  -------------

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

-------------  c++  -------------  

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;int depth = 0;queue<TreeNode*> que;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录最小深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出return depth;}}}return depth;}
};

四、226 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

题目描述：翻转这棵二叉树，并返回其根节点。

递归：1、确定参数和返回；2、确定终止条件；3、单层递归的逻辑

-------------  python  -------------

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

-------------  c++  -------------  

root->left,root->right=right,left;

C++ 不支持这种逗号表达式的赋值方式。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr) return nullptr;TreeNode*left=invertTree(root->left);TreeNode*right=invertTree(root->right);root->left=right;root->right=left;return root;}
};

--------------------------------

辅助栈迭代法：代码随想录

class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:return Nonestack=[root]while stack:node=stack.pop()if node.left:stack.append(node.left)if node.right:stack.append(node.right)node.left,node.right=node.right,node.leftreturn root

stack 不支持直接使用花括号进行初始化。正确的方法是先创建一个空栈，然后使用 push 方法添加元素，或者使用 std::vector 来初始化。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr) return nullptr;stack<TreeNode*>stk;stk.push(root);while(!stk.empty()){TreeNode*node=stk.top();stk.pop();if(node->left) stk.push(node->left);if(node->right) stk.push(node->right);TreeNode*tem=node->left;node->left=node->right;node->right=tem;}return root;}
};

五、101 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

题目描述：给定一个二叉树，检查它是否是镜像对称的。

Tips：后序遍历  正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

递归法：

-------------  python  -------------

注意检查not root (不然无法实现root.left)

我把递归的函数写成成员函数了

class Solution:def dfs(self,left,right):if left is None and right is None:return Trueif not left or not right:return Falseif left.val!=right.val:return Falsereturn self.dfs(left.left,right.right) and self.dfs(left.right,right.left)def isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truereturn self.dfs(root.left,root.right)

-------------  c++  -------------  

class Solution {
public:bool dfs(TreeNode*p,TreeNode*q){if(p==nullptr && q==nullptr) return true;  //只有一条语句可以省略大括号if(p==nullptr || q==nullptr) return false;if(p->val !=q->val) return false;return dfs(p->left,q->right) && dfs(p->right,q->left);}bool isSymmetric(TreeNode* root) {if(root==nullptr){return true;}return dfs(root->left,root->right);}
};

 和94/100的递归比较：相同的树没有使用辅助函数，没必要使用辅助函数可能是由于1、输入参数相同；2、没有其他的需要保留数据的变量如res=[ ]

迭代法：

-------------  python  -------------

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""if not root or not (root.left or root.right):return True# 用队列保存节点	queue = [root.left,root.right]while queue:# 从队列中取出两个节点，再比较这两个节点left = queue.pop(0)right = queue.pop(0)# 如果两个节点都为空就继续循环，两者有一个为空就返回falseif not (left or right):continueif not (left and right):return Falseif left.val!=right.val:return False# 将左节点的左孩子， 右节点的右孩子放入队列queue.append(left.left)queue.append(right.right)# 将左节点的右孩子，右节点的左孩子放入队列queue.append(left.right)queue.append(right.left)return True

-------------  c++  -------------   

//用vector实现
class Solution {
public:bool isSymmetric(TreeNode* root) {if(root==nullptr || (root->left==nullptr && root->right==nullptr )) return true;vector<TreeNode*> v;v.push_back(root->left);v.push_back(root->right);while(!v.empty()){TreeNode*left=v[0];v.erase(v.begin());TreeNode*right=v[0];v.erase(v.begin());//如果是v.begin()那么就需要*left->valif(left==nullptr and right==nullptr) continue;if(left==nullptr or right==nullptr) return false;if(left->val != right->val) return false;v.push_back(left->left);v.push_back(right->right);v.push_back(right->left);v.push_back(left->right);}return true;}
};
//用queue实现
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root==nullptr) return true;queue<TreeNode*>q;q.push(root->left);q.push(root->right);while(!q.empty()){TreeNode*l=q.front(); q.pop();TreeNode*r=q.front(); q.pop();if(l==nullptr && r==nullptr) continue;if(l==nullptr || r==nullptr) return false;if(l->val != r->val) return false;q.push(l->left);q.push(r->right);q.push(l->right);q.push(r->left);}return true;}
};

六、222 完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）

很容易的递归但是没有利用完全二叉树的特点：

class Solution(object):def countNodes(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0return self.countNodes(root.left)+self.countNodes(root.right)+1

完全二叉树的定义：它是一棵空树或者它的叶子节点只出在最后两层，若最后一层不满则叶子节点只在最左侧。

-------------  python  -------------

class Solution(object):def countNodes(self, root):#二叉树的层数def countlevel(root):if not root:return 0return max(countlevel(root.left),countlevel(root.right))+1if not root:return 0left=countlevel(root.left)right=countlevel(root.right)if left==right:return (1<<left)+self.countNodes(root.right)else:return (1<<right)+self.countNodes(root.left)

1<<left 是在计算pow(2,left) <<按位左移

-------------  c++  -------------   

class Solution {
public:int countlevel(TreeNode* root){if (root==nullptr) return 0;return max(countlevel(root->left),countlevel(root->right))+1;}int countNodes(TreeNode* root) {if (root==nullptr) return 0;int l=countlevel(root->left);int r=countlevel(root->right);if (l==r) return (1<<l)+countNodes(root->right);else return(1<<r)+countNodes(root->left);}
};

七、257 二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

1、递归

深度优先搜索

  • 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
  • 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可

-------------  python  -------------

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:def con_path(root,path):if root:path+=str(root.val)if not root.left and not root.right: #当前节点是叶子节点paths.append(path) #把路径加入到答案中else:path+='->' # 当前节点不是叶子节点，继续递归遍历con_path(root.left,path)con_path(root.right,path)paths=[]con_path(root,'')return paths

-------------  c++  -------------   

class Solution {
public:void construct_paths(TreeNode* root, string path, vector<string>& paths) {if (root != nullptr) {path += to_string(root->val);if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点paths.push_back(path);                              // 把路径加入到答案中} else {path += "->";  // 当前节点不是叶子节点，继续递归遍历construct_paths(root->left, path, paths);construct_paths(root->right, path, paths);}}}vector<string> binaryTreePaths(TreeNode* root) {vector<string> paths;construct_paths(root, "", paths);return paths;}
};

时间复杂度和空间复杂度都是O（N方）

2、迭代

广度优先搜索

-------------  python  -------------

代码中使用 [] 的目的是为了初始化 deque 时提供一个初始元素。

class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:paths=list()if not root:return pathsnode_queue=collections.deque([root])path_queue = collections.deque([str(root.val)])while node_queue:node = node_queue.popleft()path = path_queue.popleft()if not node.left and not node.right:paths.append(path)else:if node.left:node_queue.append(node.left)path_queue.append(path+'->'+str(node.left.val))if node.right:node_queue.append(node.right)path_queue.append(path + '->' + str(node.right.val))return paths

-------------  c++  -------------   

class Solution {
public:vector<string> paths;vector<string> binaryTreePaths(TreeNode* root) {if(root==nullptr)return {};deque<TreeNode*>nodes {root};deque<string>path {to_string(root->val)};while(!nodes.empty()){TreeNode* node=nodes.front();nodes.pop_front();string pa=path.front();path.pop_front();if(node->left==nullptr && node->right==nullptr){paths.push_back(pa);}else {if(node->left){nodes.push_back(node->left);path.push_back(pa+"->"+to_string(node->left->val));}if(node->right){nodes.push_back(node->right);path.push_back(pa+"->"+to_string(node->right->val));}}}return paths;}
};

八、404 左叶子之和

404. 左叶子之和 - 力扣（LeetCode）

题目描述：计算给定二叉树的所有左叶子之和。递归法，迭代法。代码随想录

-------------  python  -------------

# 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):if root is None:return 0if root.left is None and root.right is None:return 0leftValue = self.sumOfLeftLeaves(root.left)  # 左if root.left and not root.left.left and not root.left.right:  # 左子树是左叶子的情况leftValue = root.left.valrightValue = self.sumOfLeftLeaves(root.right)  # 右sum_val = leftValue + rightValue  # 中return sum_val

递归精简版。 

# 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):if root is None:return 0leftValue = 0if root.left is not None and root.left.left is None and root.left.right is None:leftValue = root.left.valreturn leftValue + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
# 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):if root is None:return 0st = [root]result = 0while st:node = st.pop()if node.left and node.left.left is None and node.left.right is None:result += node.left.valif node.right:st.append(node.right)if node.left:st.append(node.left)return result

-------------  c++  -------------   

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;int leftValue = 0;if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {leftValue = root->left->val;}return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
};
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;if (root == NULL) return 0;st.push(root);int result = 0;while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {result += node->left->val;}if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/18821.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

如何使用可靠UDP协议（KCP）

如何使用可靠UDP协议（KCP）

希望这篇文章&#xff0c;对学习和使用 KCP 协议的读者&#xff0c;有帮助。 1. KCPUDP 流程图 2. 示例代码 #include <iostream>int main() {// 代码太多&#xff0c;暂存仓库return 0; } 具体使用&#xff0c;请参考代码仓库&#xff1a;https://github.com/ChivenZha…
阅读更多...
论文复述：(TRPCA)t-Shatten-p

论文复述：(TRPCA)t-Shatten-p

一个基于TNN-TRPCA的简单创新的论文&#xff0c;Tensor Robust PCA主要是将一个tensor分解为low-rank和sparse两个component&#xff0c;主要思想是引入了weighted tensor Schatten-p norm进行建模。
阅读更多...
6_协议与层次划分

6_协议与层次划分

在计算机网络中要做到有条不紊地交换数据&#xff0c;就必须遵守一些事先约定好的规则。这些规则明确规定了所交换的数据的格式以及有关的同步问题。这里所说的是狭义的(即同频或同频同相) 而是广义的&#xff0c;即在一定的条件下应当发生什么事件 (例如&#xff0c;应当发送一…
阅读更多...
微服务--Gateway网关--全局Token过滤器【重要】

微服务--Gateway网关--全局Token过滤器【重要】

全局过滤器 GlobalFilter&#xff0c; 注入到 IOC里面即可 概念&#xff1a; 全局过滤器&#xff1a; 所有的请求 都会在执行链里面执行这个过滤器 如添加日志、鉴权等 创建一个全局过滤器的基本步骤&#xff1a; 步骤1: 创建过滤器类 首先&#xff0c;创建一个实现了Globa…
阅读更多...
Kafka进阶_1.生产消息

Kafka进阶_1.生产消息

文章目录 一、Controller选举二、生产消息2.1、创建待发送数据2.2、创建生产者对象&#xff0c;发送数据2.3、发送回调2.3.1、异步发送2.3.2、同步发送 2.4、拦截器2.5、序列化器2.6、分区器2.7、消息可靠性2.7.1、acks 02.7.2、acks 1(默认)2.7.3、acks -1或all 2.8、部分重…
阅读更多...
STL C++ CookBook 7:迭代器简论

STL C++ CookBook 7:迭代器简论

目录 兼容的迭代器 迭代器概念 使用迭代器来填充STL的容器 将一些序列算法包装成可迭代的 构建 zip 迭代器适配器 兼容的迭代器 迭代器是 STL 中的一个基本概念。迭代器使用 C 指针的语义实现&#xff0c;使用相同的递增、递减和解引用运算符。 大多数 C/C 程序员都熟悉指…
阅读更多...
【Python图解】 常量与变量及基本运算

【Python图解】 常量与变量及基本运算

【图解python】 常量与变量及基本运算 Python 常量与变量教程 可能你现在会产生疑惑&#xff0c;代码中的 print 代表什么意义&#xff1f;括号又是什么作用&#xff1f;为什么 hello world 外面有个双引号&#xff1f;没关系&#xff0c;下面我们就来了解 Python 语法的奥秘…
阅读更多...
「漏洞复现」全新优客API接口管理系统 index/doc SQL注入漏洞

「漏洞复现」全新优客API接口管理系统 index/doc SQL注入漏洞

0x01 免责声明 请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;作者不为此承担任何责任。工具来自网络&#xff0c;安全性自测&#xff0c;如有侵权请联系删…
阅读更多...
java ssm 健康医馆管理系统 中医馆管理 健康平台 药店 源码jsp

java ssm 健康医馆管理系统 中医馆管理 健康平台 药店 源码jsp

一、项目简介 本项目是一套基于SSM的健康医馆管理系统&#xff0c;主要针对计算机相关专业的和需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本、软件工具等。 项目都经过严格调试&#xff0c;确保可以运行&#xff01; 二、技术实现 ​后端技术&#x…
阅读更多...
Python - jieba库的使用

Python - jieba库的使用

文章目录 jieba库概述jieba分词的三种模式jieba库的安装 jieba分词的原理jieba库常用函数实例 : 文本词频统计 jieba库概述 jieba是优秀的中文分词第三方库 中文文本需要通过分词获得单个的词语jieba是优秀的中文分词第三方库&#xff0c;需要额外安装jieba库提供三种分词模式…
阅读更多...
一个简单的图像分类项目（九）并行训练的学习：多GPU的DP（DataParallel数据并行）

一个简单的图像分类项目（九）并行训练的学习：多GPU的DP（DataParallel数据并行）

将电脑装成Ubuntu、Windows双系统&#xff0c;并在Ubuntu上继续学习。 在现代深度学习中&#xff0c;多主机多GPU训练已经变得非常常见&#xff0c;尤其是对于大规模模型和数据集。最简单和早期的并行计算比如NVIDIA的SLI&#xff0c;从NVIDIA 450系列驱动开始&#xf…
阅读更多...
本草智选：中药实验管理的智能推荐

本草智选：中药实验管理的智能推荐

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了中药实验管理系统的开发全过程。通过分析中药实验管理系统管理的不足&#xff0c;创建了一个计算机管理中药实验管理系统的方案。文章介绍了中药实验管理系统的系…
阅读更多...
凸优化理论和多模态基础模型研究

凸优化理论和多模态基础模型研究

文章目录 摘要Abstract1. 拉格朗日对偶问题1.1 弱对偶问题1.2 强对偶问题&#xff08;P*D*&#xff09;1.3 KKT条件 2. 论文阅读3. 总结 摘要 本周从拉格朗日对偶理论出发&#xff0c;系统学习了优化问题中凸函数、强对偶条件以及 KKT 条件的应用&#xff0c;并将其与机器学习…
阅读更多...
nginx+vconsole调试网页在vivo浏览器无法显示图片问题

nginx+vconsole调试网页在vivo浏览器无法显示图片问题

一、问题描述 昨天测试小伙伴提了一个特殊的bug&#xff0c;在安卓vivo手机浏览器上访问网页&#xff0c;网页的图片按钮和录播图一闪而过后便消失不见&#xff1a; 二、问题排查 项目采用Nuxt框架&#xff0c;排查的方向大致如下&#xff1a; 1.其它手机浏览器是否有复现&am…
阅读更多...
草本追踪：中药实验管理的数字化转型

草本追踪：中药实验管理的数字化转型

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…
阅读更多...
【Linux】虚拟地址空间，页表，物理内存

【Linux】虚拟地址空间，页表，物理内存

目录 进程地址空间&#xff0c;页表&#xff0c;物理内存 什么叫作地址空间&#xff1f; 如何理解地址空间的区域划分&#xff1f; 地址空间结构体 为什么要有地址空间&#xff1f; 页表 cr3寄存器 权限标记位 位置标记位 其他 每个存储单元是一个字节&#xff0c;一…
阅读更多...
集群聊天服务器(3)muduo网络库

集群聊天服务器(3)muduo网络库

目录 基于muduo的客户端服务器编程 muduo只能装在linux中&#xff0c;依赖boost库 客户端并不需要高并发 基于muduo的客户端服务器编程 支持epoll线程池&#xff0c;muduo封装了线程池 而且还有完善的日志系统 使用muduo库代码非常固定&#xff0c;基本就只有chatserver的类名…
阅读更多...
【Python刷题】最少拐弯路线问题

【Python刷题】最少拐弯路线问题

题目描述 洛谷P1649 一、题目理解 首先&#xff0c;我们来看一下这道题目的要求。题目给定了一个 NN&#xff08;1≤N≤100&#xff09; 的方格&#xff0c;方格中的每个格子有不同的状态&#xff0c;用 . 表示可以行走的格子&#xff0c;x 表示不能行走的格子&#xff0c;…
阅读更多...
在windows系统里面部署 Redis

在windows系统里面部署 Redis

在windows中下载安装REdis 1.下载mis 地址添加链接描述 然后直接下载安装然后点击你的库 2.然后选择好之后选择好路径就行了。 然后我们点击这个cli.exe文件然后双击打开输入 在命令框里输入&#xff1a; 如果显示的和图片显示的一样&#xff0c;则证明你已经在本地部署好了…
阅读更多...
NTP博客

NTP博客

使用nmtui命令修改IP&#xff1a; 注意&#xff1a; 修改之后&#xff0c;要激活&#xff1a; nmcli connection up ens160 1、软件安装 #设置当前时区 [rootlocalhost ~]# timedatectl set-timezone Asia/Shanghai 1.1.配置国内阿里yum源 [rootredhat ~]# cd /etc/yum.r…
阅读更多...
最新文章

Copyright @ 2022~2023