跳转至

Day14 | Part4

约 137 个字 70 行代码 预计阅读时间 1 分钟

110.平衡二叉树

每一个节点的左右子树高度差的绝对值不超过1 → 高度VS深度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int getDepth(TreeNode* node) {
    if(!node) return 0;
    return 1 + max(getDepth(node->left), getDepth(node->right));
}
bool isBalanced(TreeNode* root) {
    if(!root) return true;
    int l = getDepth(root->left), r = getDepth(root->right);
    return abs(l - r) <= 1 
            && isBalanced(root->left) 
            && isBalanced(root->right);
}

257.二叉树的所有路径

需要 回溯 即回退进入另一个路径,可作为函数参数进行传递,参考

递归: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void traverse(vector<string>& res, TreeNode* root, string t) {
    if(!root->left && !root->right) {
        res.push_back(t);
        return;
    }
    if(root->left)
        traverse(res, root->left, t + "->" + to_string(root->left->val));
    if(root->right) 
        traverse(res, root->right, t + "->" + to_string(root->right->val));
}
vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> res;
    if(!root) return res;
    traverse(res, root, to_string(root->val));
    return res;
}

迭代: 利用栈一个保存遍历的节点一个保存路径对应的值 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> res;
    stack<TreeNode*> st;
    stack<string> path;
    if(!root) return res;
    st.push(root), path.push(to_string(root->val));
    while(!st.empty()) {
        auto node = st.top(); st.pop();
        string p = path.top(); path.pop();
        if(!node->left && !node->right) res.push_back(p);
        if(node->left) {
            st.push(node->left);
            path.push(p + "->" + to_string(node->left->val));
        }
        if(node->right) {
            st.push(node->right);
            path.push(p + "->" + to_string(node->right->val));
        }
    }
    return res;
}

404.左叶子之和

节点A的左孩子不为空,且左孩子的左右孩子都为空,则A节点的左孩子为左叶子节点

递归: 

1
2
3
4
5
6
7
8
int sumOfLeftLeaves(TreeNode* root) { 
    if(!root) return 0;
    if(!root->left && !root->right) return 0;
    int l = sumOfLeftLeaves(root->left), r = sumOfLeftLeaves(root->right);
    if(root->left && !root->left->left && !root->left->right) 
        l = root->left->val;
    return l + r;
}

迭代: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int sumOfLeftLeaves(TreeNode* root) {
    int sum = 0;
    stack<TreeNode*> st;
    if(!root) return 0;
    st.push(root);
    while(!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        if(node->left && !node->left->left && !node->left->right)
            sum += node->left->val;
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }
    return sum;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论