《代码随想录》刷题打卡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, vectorint path, vectorstring 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();// 回溯 } } vectorstring binaryTreePaths(TreeNode* root) { vectorint path; vectorstring 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; stackTreeNode* 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; queueTreeNode* 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; }