Day17 二叉樹第四天
LeetCode 110. 平衡二叉樹【后序遍歷】
平衡二叉樹仍是后序遍歷,就是獲取左右子樹的高度然后作差,如果子樹就不平衡,那么就直接將-1向上傳給父節點,否則該數的高度為左右子樹高度的最大值+1。
class Solution {
public:int getHeight(TreeNode* node){if(!node) return 0;int leftHeight=getHeight(node->left);if(leftHeight==-1) return -1;int rightHeight=getHeight(node->right);if(rightHeight==-1) return -1;if(abs(rightHeight-leftHeight)>1) return -1;else return 1+max(rightHeight,leftHeight);}bool isBalanced(TreeNode* root) {return getHeight(root)==-1?false:true;}
};
LeetCode 257.二叉樹的所有路徑 【前序遍歷】
首次遇到回溯過程,我們在遍歷完之后要將元素彈出,這樣才能保證遍歷往回走時節點也彈出了。
本題有幾點需要注意:
1.遞歸推出的條件是節點左右節點均為空,而不是節點為空。
2.前序遍歷時【中】的過程,也就是記錄節點的過程要寫在遞歸結束判斷之前,否則會遺落葉子結點。
3.注意回溯的過程。
class Solution {
public:vector<int> path;vector<string> res;void travesal(TreeNode* node,vector<int>& path,vector<string>& res){path.push_back(node->val);if(!node->left && !node->right){string sPath;for(int i=0;i<path.size()-1;i++){sPath+=to_string(path[i]);sPath+="->";}sPath+=to_string(path[path.size()-1]);res.push_back(sPath);return;}if(node->left){travesal(node->left,path,res);path.pop_back();}if(node->right){travesal(node->right,path,res);path.pop_back();}}vector<string> binaryTreePaths(TreeNode* root) {if(!root) return res;travesal(root,path,res);return res;}
};
LeetCode 404.左葉子之和【后序遍歷】
本題的難點在于處理這個節點時,我們只能知道他是葉子,無法確定是否是左葉子,所以我們必須在處理他的父節點時處理這個節點,也就是如果一個節點的左孩子不為空,且這個左孩子是葉子節點,就把他的數值加到這棵樹的左葉子之和中,最后這棵樹的左葉子之和就是左右孩子的左葉子之和的和。
也就是說如果我們處理到了葉子節點,那么直接返回0即可,不必再向下遞歸一層。因為我們已經在葉子結點的上一層獲取到了左葉子的和。這樣可以減少遞歸次數,使代碼效率更高。
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(!root) return 0;if(!root->left && !root->right) return 0;int leftSum=sumOfLeftLeaves(root->left);if(root->left && !root->left->left && !root->left->right)leftSum=root->left->val;int rightSum=sumOfLeftLeaves(root->right);int sum=leftSum+rightSum;return sum;}
};
在寫樹和遞歸的過程中,要多注意題目的細節。