《代码随想录》刷题打卡day13：二叉树part03
文章目录
- 【平衡二叉树】
- 【二叉树的所有路径】
- 【左叶子之和】
- 【完全二叉树的节点个数】
【平衡二叉树】
求深度适合用前序遍历，而求高度适合用后序遍历。
回溯通常都不用迭代法，递归一定要掌握！
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-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; }【二叉树的所有路径】
思路：
- 来一个节点，先存进路径
- 到叶子节点，就把路径存起来
- 走完一条路，必须回退一步（回溯），再走另一条路
回溯和递归是一一对应的，有一个递归，就要有一个回溯
void travelsal(TreeNode* cur, vector<int>& path, vector<string>& result){ path.push_back(cur->val);// 中，中为什么写在这里，因为最后一个节点也要加入到path中 // 说明到了叶子结点 if(cur->left == nullptr && cur->right == nullptr){ string sPath; for(int i = 0;i < path.size() - 1;i++){ sPath += to_string(path[i]); sPath += "->"; } sPath += to_string(path[path.size() - 1]); result.push_back(sPath); } // 未到叶子结点 if(cur->left){ travelsal(cur->left, path, result); path.pop_back();// 回溯 } if(cur->right){ travelsal(cur->right, path, result); path.pop_back();// 回溯 } } vector<string> binaryTreePaths(TreeNode* root) { vector<int> path; vector<string> result; if(root == nullptr) return result; travelsal(root, path, result); return result; }【左叶子之和】
思路：
- 遍历二叉树所有节点（栈 / 递归都行）
- 对每个节点，只看它的左孩子
- 判断左孩子是不是左叶子
- 是 → 加到 sum
- 不是 → 不管
- 继续遍历右孩子
- 最后返回 sum
递归法：
int sumOfLeftLeaves(TreeNode* root) { if(root == nullptr) return 0;// 如果当前节点是空节点，左叶子必然是0 if(root->left == nullptr && root->right == nullptr) return 0;// 如果父节点是叶子结点，其左叶子也必然是0 int leftValue = sumOfLeftLeaves(root->left); if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){// 左子树就是一个左叶子的情况 leftValue = root->left->val; } int rightValue = sumOfLeftLeaves(root->right); int sum = leftValue + rightValue; return sum; }迭代法：
int sumOfLeftLeaves(TreeNode* root) { if(root == nullptr) return 0; stack<TreeNode*> st; st.push(root); int sum = 0; while(!st.empty()){ TreeNode* cur = st.top(); st.pop(); if(cur->left){ st.push(cur->left); if(!cur->left->left && !cur->left->right){ sum += cur->left->val; st.pop(); } } if(cur->right){ st.push(cur->right); } } return sum; }【完全二叉树的节点个数】
递归法：最大深度略加修改
int getNodesSum(TreeNode* cur){ if(cur == nullptr) return 0; int leftNum = getNodesSum(cur->left); int rightNum = getNodesSum(cur->right); int TreeNum = leftNum + rightNum + 1; return TreeNum; } int countNodes(TreeNode* root) { return getNodesSum(root); }迭代法：层序遍历模板略加修改
int countNodes(TreeNode* root) { if(root == nullptr) return 0; queue<TreeNode*> que; que.push(root); int sum = 0; while(!que.empty()){ int size = que.size(); for(int i = 0; i < size; i++){ TreeNode* node = que.front(); sum++; que.pop(); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } } return sum; }