爱站网站排名查询工具,写文案要看的网站,the field wordpress,wordpress自动推送满二叉树#xff1a;如果一棵二叉树只有度为0的结点和度为2的结点#xff0c;并且度为0的结点在同一层上#xff0c;则这棵二叉树为满二叉树。深度为k#xff0c;有2^k-1个节点的二叉树。
完全二叉树#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外如果一棵二叉树只有度为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, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint 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, vectorint 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, vectorint 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)rootroot.leftelse:temstack.pop()roottem.rightreturn res
------------- c -------------
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {if(rootnullptr) return {};stackTreeNode* stk;vectorint res;while(!stk.empty() || root){ //stack不可以转换成bool类型if (root){res.push_back(root-val);stk.push(root);rootroot-left;}else{TreeNode* temstk.top();stk.pop();roottem-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:vectorint inorderTraversal(TreeNode* root) {vectorintres;stackTreeNode*stk;while(root!nullptr || !stk.empty()){if(root!nullptr){stk.push(root);rootroot-left;}else{rootstk.top();stk.pop();res.push_back(root-val);rootroot-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:vectorint res;void dfs(TreeNode* root){if(rootnullptr) return;dfs(root-left);dfs(root-right);res.push_back(root-val);}vectorint postorderTraversal(TreeNode* root) {if(rootnullptr) return {};dfs(root);return res;}
};
三、二叉树的层序遍历
1、102 二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣LeetCode
需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
------------- python -------------
# 利用长度法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint 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, vectorvectorint result, int depth){if (cur nullptr) return;if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result, depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint 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, val0, leftNone, rightNone):
# 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:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint 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:vectorint rightSideView(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorint 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, val0, leftNone, rightNone):
# 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:vectordouble averageOfLevels(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectordouble 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:vectorvectorint levelOrder(Node* root) {queueNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint 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:vectorint largestValues(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorint 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) {queueNode* que;if (root ! NULL) que.push(root);while (!que.empty()) {int size que.size();// vectorint 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) {queueNode* que;if (root ! NULL) que.push(root);while (!que.empty()) {int size que.size();vectorint 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;queueTreeNode* 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;queueTreeNode* 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 Noneleftself.invertTree(root.left)rightself.invertTree(root.right)root.left,root.rightright,leftreturn root
------------- c -------------
root-left,root-rightright,left;
C 不支持这种逗号表达式的赋值方式。
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(rootnullptr) return nullptr;TreeNode*leftinvertTree(root-left);TreeNode*rightinvertTree(root-right);root-leftright;root-rightleft;return root;}
};
--------------------------------
辅助栈迭代法代码随想录
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:if not root:return Nonestack[root]while stack:nodestack.pop()if node.left:stack.append(node.left)if node.right:stack.append(node.right)node.left,node.rightnode.right,node.leftreturn root
stack 不支持直接使用花括号进行初始化。正确的方法是先创建一个空栈然后使用 push 方法添加元素或者使用 std::vector 来初始化。
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(rootnullptr) return nullptr;stackTreeNode*stk;stk.push(root);while(!stk.empty()){TreeNode*nodestk.top();stk.pop();if(node-left) stk.push(node-left);if(node-right) stk.push(node-right);TreeNode*temnode-left;node-leftnode-right;node-righttem;}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(pnullptr qnullptr) return true; //只有一条语句可以省略大括号if(pnullptr || qnullptr) 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(rootnullptr){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: boolif 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(rootnullptr || (root-leftnullptr root-rightnullptr )) return true;vectorTreeNode* v;v.push_back(root-left);v.push_back(root-right);while(!v.empty()){TreeNode*leftv[0];v.erase(v.begin());TreeNode*rightv[0];v.erase(v.begin());//如果是v.begin()那么就需要*left-valif(leftnullptr and rightnullptr) continue;if(leftnullptr or rightnullptr) 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 (rootnullptr) return true;queueTreeNode*q;q.push(root-left);q.push(root-right);while(!q.empty()){TreeNode*lq.front(); q.pop();TreeNode*rq.front(); q.pop();if(lnullptr rnullptr) continue;if(lnullptr || rnullptr) 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: intif 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 0leftcountlevel(root.left)rightcountlevel(root.right)if leftright:return (1left)self.countNodes(root.right)else:return (1right)self.countNodes(root.left)
1left 是在计算pow(2,left) 按位左移
------------- c -------------
class Solution {
public:int countlevel(TreeNode* root){if (rootnullptr) return 0;return max(countlevel(root-left),countlevel(root-right))1;}int countNodes(TreeNode* root) {if (rootnullptr) return 0;int lcountlevel(root-left);int rcountlevel(root-right);if (lr) return (1l)countNodes(root-right);else return(1r)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:pathstr(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, vectorstring 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);}}}vectorstring binaryTreePaths(TreeNode* root) {vectorstring paths;construct_paths(root, , paths);return paths;}
};时间复杂度和空间复杂度都是ON方
2、迭代
广度优先搜索
------------- python -------------
代码中使用 [] 的目的是为了初始化 deque 时提供一个初始元素。
class Solution:def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]:pathslist()if not root:return pathsnode_queuecollections.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:vectorstring paths;vectorstring binaryTreePaths(TreeNode* root) {if(rootnullptr)return {};dequeTreeNode*nodes {root};dequestringpath {to_string(root-val)};while(!nodes.empty()){TreeNode* nodenodes.front();nodes.pop_front();string papath.front();path.pop_front();if(node-leftnullptr node-rightnullptr){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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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) {stackTreeNode* 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;}
};
