标签：node right TreeNode int 随想录节点二叉树 257 left

代码随想录算法训练营Day17|110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和

110. 平衡二叉树

本题要比较左右子树的高度，首先明确高度和深度的区别：

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

110.平衡二叉树2

关于根节点的深度，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，暂时以leetcode为准。

①递归法

明确递归三要素：

明确递归函数的参数和返回值

参数：当前传入节点。

返回值：以当前传入节点为根节点的树的高度。

那么如何标记左右子树是否差值大于1呢？

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

代码如下：

// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)

明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

代码如下：

if (node == NULL) {
    return 0;
}

明确单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。

代码如下：

int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) return -1;

int result;
if (abs(leftHeight - rightHeight) > 1) {  // 中
    result = -1;
} else {
    result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}

return result;

完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        int res = getDepth(root);
        if (res == -1) return false;
        else return true;
    }

    // 在求高度的过程中进行判断
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);
        if (leftDepth == -1) return -1;
        int rightDepth = getDepth(node->right);
        if (rightDepth == -1) return -1;
        if (abs(leftDepth - rightDepth) > 1) return -1;
        else return max(leftDepth, rightDepth) + 1;
    }
};

257. 二叉树的所有路径

递归法，确定递归三要素：

传入参数

我们用vector<int>&记录一条路径上涉及的所有节点，用vector<string>&记录所有路径的合集，因为两个参数都是引用传递，所以向下遍历后我们需要控制回溯。

257.二叉树的所有路径

终止条件

这里需要一直递归到叶子结点，所以终止条件就需要设置成判断左右孩子节点同时为空：

if (node->left == NULL && node->right == NULL)

至于节点为空的情况，我们可以在遍历左右孩子节点的时候进行判断，根节点则在调用递归函数前进行讨论即可：

if (node->left) traversal(node->left);
if (node->right) traversal(node->right);

确定单层的递归逻辑

因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。

path.push_back(cur->val);

然后是递归和回溯的过程，上面说过没有判断cur是否为空，那么在这里递归的时候，如果为空就不进行下一层递归了。

所以递归前要加上判断语句，下面要递归的节点是否为空，如下

if (cur->left) {
    traversal(cur->left, path, result);
}
if (cur->right) {
    traversal(cur->right, path, result);
}

这里为了体现路径回溯的特征，需要在每次遍历孩子节点后，将数组末尾新加入的节点弹出，这里使用到vector中的pop_back()函数，注意回溯和递归是一一对应的，有一个递归，就要有一个回溯，代码如下：

if (cur->left) {
    traversal(cur->left, path, result);
    path.pop_back(); // 回溯
}
if (cur->right) {
    traversal(cur->right, path, result);
    path.pop_back(); // 回溯
}

完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        vector<int> path;
        if (root == NULL) return res;
        traversal(root, path, res);
        return res;
    }

    void traversal(TreeNode* node, vector<int>& path, vector<string>& res) {
        // 判断前需要把当前节点也加入路径末尾
        path.push_back(node->val);
        if (node->left == NULL && node->right == NULL) {
            // 将path串成字符串
            string str;
            for (int i = 0; i < path.size() - 1; i++) {
                str += to_string(path[i]);
                str += "->";
            }
            str += to_string(path[path.size() - 1]);
            res.push_back(str);
            return;
        }
        if (node->left) {
            traversal(node->left, path, res);
            // 回溯遍历节点
            path.pop_back();
        }
        if (node->right) {
            traversal(node->right, path, res);
            path.pop_back();
        }
    }
};

另外，也可以考虑不使用引用传递路径，避免了路径回溯的步骤，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        if (root == NULL) return res;
        string str = "";
        searchTree(root, str);
        return res;
    }

    void searchTree(TreeNode* node, string str) {
        // 给头结点指定单独的插入策略
        if (str == "") str += to_string(node->val);
        else {
            str += "->";
            str += to_string(node->val);
        }
        cout << str << endl;
        if (node->left == NULL && node->right == NULL) {
            res.push_back(str);
            return;
        }
        if (node->left) searchTree(node->left, str);
        if (node->right) searchTree(node->right, str);
        return;
    }
public:
    vector<string> res;
};

404. 左叶子之和

递归法，确定递归三部曲：

确定递归函数的参数和返回值

判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int

使用题目中给出的函数就可以了。

确定终止条件

如果遍历到空节点，那么左叶子值一定是0

if (root == NULL) return 0;

注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：

确定单层递归的逻辑

当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。关键在于怎么判断左孩子节点，这需要在该节点的父节点基础上进行判断：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
    左叶子节点处理逻辑
}

完整代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        searchTree(root);
        return sum;
    }

    void  searchTree(TreeNode* node) {
        if (node == NULL) return;
        if (node->left != NULL 
        && node->left->left == NULL 
        && node->left->right == NULL) 
            sum += node->left->val;
        searchTree(node->left);
        searchTree(node->right);
    }

public:
    int sum = 0;
};

这里也可以考虑将递归函数整合成一个函数：每次遍历左右孩子节点，然后根据左孩子节点的判断规则，递归地返回左孩子节点的值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right);
        // 关键在对左孩子节点的判断来刷新节点值
        // 无论左/右孩子目标都是判断左孩子
        if (root->left != NULL && 
        root->left->left == NULL && root->left->right == NULL)
            // 直接刷新左孩子节点数值
            leftValue = root->left->val;
        return leftValue + rightValue;
    }
};

标签：node,right,TreeNode,int,随想录,节点,二叉树,257,left
From： https://www.cnblogs.com/buryinshadow/p/16967297.html

代码随想录算法训练营Day17|110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和

代码随想录算法训练营Day17|110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和

110. 平衡二叉树

257. 二叉树的所有路径

404. 左叶子之和

相关文章

赞助商

阅读排行