资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

代码随想录算法训练营第三期day17-二叉树04-创新互联

目录

创新互联致力于做网站、成都网站设计,成都网站设计,集团网站建设等服务标准化，推过标准化降低中小企业的建站的成本，并持续提升建站的定制化服务水平进行质量交付，让企业网站从市场竞争中脱颖而出。 选择创新互联，就选择了安全、稳定、美观的网站建设服务！

1、T110：平衡二叉树

法1、递归

法2、迭代

2、T257：二叉树的所有路径

法1、递归

Ⅰ、版本1【最容易理解】

Ⅱ、版本2【分为隐式和显式】

法2、迭代

3、T404：左叶子之和

法1、递归

法2、迭代（反正没有顺序要求，用队列或栈都行）

Ⅰ、队列层序遍历（本人的本能）

Ⅱ、栈迭代

1、T110：平衡二叉树

T110：给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

提示：

  • 树中的节点数在范围 [0, 5000] 内

  • -104 <= Node.val<= 104

S：

法1、递归

既然要求比较高度，理应是要用后序遍历

C++：

bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        int leftHeigt = getHeight(node->left);
        if (leftHeigt == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;

        return abs(leftHeigt - rightHeight) >1 ? -1 : 1 + max(leftHeigt, rightHeight);
        // 以当前节点为根节点的树的大高度
    }

Java：

public boolean isBalanced(TreeNode root) {
        return getHeight(root) == -1 ? false : true;
    }
    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 Math.abs(leftHeight - rightHeight) >1 ? -1 : Math.max(leftHeight, rightHeight);
        // 🚩用上一行就错！因为有可能出现leftHeight和rightHeight均为-1的情况
        return Math.abs(leftHeight - rightHeight) >1 ? -1 : 1 + Math.max(leftHeight, rightHeight); 
    }
法2、迭代

我们可以使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出求高度和求深度的不同。

本题的迭代方式可以先定义一个函数，专门用来求高度。

这个函数通过栈模拟的后序遍历找每一个节点的高度（其实是通过求传入节点为根节点的大深度来求的高度）

C++：

bool isBalanced(TreeNode* root) {
        if (!root) return true;
        stackst;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();

            if (abs(getHeight(node->left) - getHeight(node->right)) >1) {
                return false;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return true;
    }
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        stackst;
        st.push(node);
        int res = 0;
        int height = 0;
        while (!st.empty()) {
            TreeNode* cur = st.top();
            if (cur) {
                st.pop();
                st.push(cur);
                st.push(nullptr);
                ++height;
                // st.push(cur->right);
                // st.push(cur->left);
                if (cur->right) st.push(cur->right);
                if (cur->left) st.push(cur->left);
            } else {
                st.pop();
                cur = st.top();
                st.pop();
                // res = res >height ? res : height;
                --height;//回溯
            }
            res = res >height ? res : height;
            // --height;
        }
        return res;
    }

此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

2、T257：二叉树的所有路径

T257：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

S：

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一一个路径在进入另一个路径。

法1、递归 Ⅰ、版本1【最容易理解】

C++：

vectorbinaryTreePaths(TreeNode* root) {
        vectorres;
        if (!root) return res;
        vectorpaths;
        traversal(root, paths, res);
        return res;
    }
    // void traversal(TreeNode* node, vectorpaths, vectorres) {//别又犯病！
    void traversal(TreeNode* node, vector& paths, vector& res) {
        paths.push_back(node->val);
        if (!node->left && !node->right) {
            string path;
            for (int i = 0; i< paths.size() - 1; ++i) {
                path += to_string(paths[i]);
                path += "->";
            }
            path += to_string(paths[paths.size() - 1]);
            res.push_back(path);
            return;
        }
        if (node->left) {
            traversal(node->left, paths, res);
            paths.pop_back();// 回溯
        }
        if (node->right) {
            traversal(node->right, paths, res);
            paths.pop_back();// 回溯
        }
    }

Java：

public ListbinaryTreePaths(TreeNode root) {
        Listres = new LinkedList<>();
        if (root == null) return res;
        Listpaths = new LinkedList<>();
        traversal(root, paths, res);
        return res;
    }
    void traversal(TreeNode node, Listpaths, Listres) {
        paths.add(node.val);
        if (node.left == null && node.right == null) {
            StringBuilder path = new StringBuilder();
            //最后一个不能再接箭头
            for (int i = 0; i< paths.size() - 1; ++i) {
                path.append(paths.get(i));
                path.append("->");
            }
            path.append(paths.get(paths.size() - 1));
            res.add(path.toString());
        }
        if (node.left != null) {
            traversal(node.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (node.right != null) {
            traversal(node.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
Ⅱ、版本2【分为隐式和显式】

1、隐式回溯

C++：

vectorbinaryTreePaths(TreeNode* root) {
        vectorres;
        if (!root) return res;
        string path;
        traversal(root, path, res);
        return res;
    }

    // void traversal(TreeNode* node, string& path, vector& res) {//🚩不要用引用，这很重要！！！
    void traversal(TreeNode* node, string path, vector& res) {
        // path += node->val;
        path += to_string(node->val);
        if (!node->left && !node->right) {
            res.push_back(path);
            return;
        }
        if (node->left) {
            traversal(node->left, path + "->", res);
        }
        if (node->right) {
            traversal(node->right, path + "->", res);
        }
    }

代码精简了不少，也隐藏了不少东西。

在函数定义的时候 void traversal(TreeNode* cur, string path, vector& result) ，定义的是string path，每次都是复制赋值（~值传递），不用使用引用，否则就无法做到回溯的效果。

在上面的代码中，貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->"。 每次函数调用完，path依然是没有加上"->" 的，这就是回溯了。

Java：

public ListbinaryTreePaths(TreeNode root) {
        Listres = new ArrayList<>();
        if (root == null) return res;
        String path = "";
        traversal(root, path, res);
        return res;
    }
    void traversal(TreeNode node, String path, Listres) {
        path += node.val;
        if (node.left == null && node.right == null) {
            res.add(path);
            return;
        }
        if (node.left != null) {
            traversal(node.left, path + "->", res);//🚩不会改变外面的path！
        }
        if (node.right != null) {
            traversal(node.right, path + "->", res);
        }
    }

2、显式回溯

C++：

vectorbinaryTreePaths(TreeNode* root) {
        vectorres;
        if (!root) return res;
        string path;
        traversal(root, path, res);
        return res;
    }
    void traversal(TreeNode* node, string path, vector& res) {
        path += to_string(node->val);
        if (!node->left && !node->right) {
            res.push_back(path);
            return;
        }
        if (node->left) {
            // traversal(node->left, path + "->", res);
            path += "->";
            traversal(node->left, path, res);
            path.pop_back();
            path.pop_back();
        }
        if (node->right) {
            // traversal(node->right, path + "->", res);
            path += "->";
            traversal(node->right, path, res);🚩里面+=不会改变外面的path！
            path.pop_back();
            path.pop_back();
        }

    }

Java：不能用StringBuilder（如下，反正本人是用失败了，毕竟数字不是一定只有一位的）

失败版：

public ListbinaryTreePaths(TreeNode root) {
        Listres = new ArrayList<>();
        if (root == null) return res;
        StringBuilder path = new StringBuilder();
        traversal(root, path, res);
        return res;
    }
    void traversal(TreeNode node, StringBuilder path, Listres) {
        path.append(node.val);
        if (node.left == null && node.right == null) {
            res.add(path.toString());
            return;
        }
        if (node.left != null) {
            path.append("->");
            traversal(node.left, path, res);
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
            // path.deleteCharAt(path.length() - 1);
        }
        if (node.right != null) {
            path.append("->");
            traversal(node.right, path, res);
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
            // path.deleteCharAt(path.length() - 1);
        }
    }

通过版：

public ListbinaryTreePaths(TreeNode root) {
        Listres = new ArrayList<>();
        if (root == null) return res;
        String path = "";
        traversal(root, path, res);
        return res;
    }
    void traversal(TreeNode node, String path, Listres) {
        path += node.val;
        if (node.left == null && node.right == null) {
            res.add(path);
            return;
        }
        if (node.left != null) {
            path += "->";
            traversal(node.left, path, res);
            path = path.substring(0, path.length() - 2);//该方法是左闭右开区间
        }
        if (node.right != null) {
            path += "->";
            traversal(node.right, path, res);
            path = path.substring(0, path.length() - 2);
        }
    }
法2、迭代

除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。

C++：

vectorbinaryTreePaths(TreeNode* root) {
        vectorres;
        if (!root) return res;
        stacktreeSt;
        stackpathSt;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top();// 取出节点 中
            treeSt.pop();
            string path = pathSt.top();// 取出该节点对应的路径
            pathSt.pop();
            if (!node->left && !node->right) {
                res.push_back(path);
            }
            if (node->right) {// 右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            if (node->left) {// 左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }
        return res;
    }

Java：

public ListbinaryTreePaths(TreeNode root) {
        Listres = new ArrayList<>();
        if (root == null) return res;
        Dequenodes = new LinkedList<>();
        nodes.offerFirst(root);
        Dequepaths = new LinkedList<>();
        paths.offerFirst(String.valueOf(root.val));
        // paths.offerFirst(root.val + "");
        
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            String path = paths.poll();
            if (node.left == null && node.right == null) {
                res.add(path);
            }
            if (node.right != null) {//右
                // path += "->";
                // path += node.right.val;
                // paths.push(path);
                nodes.push(node.right);
                paths.push(path + "->" + node.right.val);
            }
            if (node.left != null) {//左
                // path += "->";
                // path += node.left.val;//不知为何用这两行就不对
                // paths.push(path);
                nodes.push(node.left);
                paths.push(path + "->" + node.left.val);
            }
        }
        return res;
    }

如上所示，不知为何按照

3、T404：左叶子之和

T404：给定二叉树的根节点 root ，返回所有左叶子之和。

提示:

  • 节点数在 [1, 1000] 范围内

  • -1000<= Node.val<= 1000

S：

首先要清楚左叶子的定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点

法1、递归

递归的遍历顺序为后序（左右中），因为要通过递归函数的返回值来累加求取左叶子数值之和。

遇到左叶子节点的时候，记录数值，然后递归求 左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

C++：

int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int leftValue = sumOfLeftLeaves(root->left);// 左
        if (root->left && !root->left->left && !root->left->right) {// 左子树就是一个左叶子的情况
            leftValue = root->left->val;//可能不理解为什么要替掉，也可以用midValue（见Java版）
        }
        int rightValue = sumOfLeftLeaves(root->right);// 右
        return leftValue + rightValue;// 中
    }

//->【精简版】
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int leftValue = 0;
        if (root->left && !root->left->left && !root->left->right) {
            leftValue = root->left->val;
        }
        return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }

Java：

public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 0;//有没有都行
        int midValue = 0, leftValue = 0, rightValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            midValue = root.left.val;
        }
        if (root.left != null) {
            leftValue = sumOfLeftLeaves(root.left);
        }
        if (root.right != null) {
            rightValue = sumOfLeftLeaves(root.right);
        }
        return midValue + leftValue + rightValue;
    }
法2、迭代（反正没有顺序要求，用队列或栈都行） Ⅰ、队列层序遍历（本人的本能）

C++：

int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        queueque;
        que.push(root);
        int sum = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i< size; ++i) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) {
                    que.push(node->left);
                    if (!node->left->left && !node->left->right) {//必须！
                        sum += node->left->val;
                    }
                }
                if (node->right) que.push(node->right);
            }
        }
        return sum;
    }
Ⅱ、栈迭代

C++：

int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        stackst;
        st.push(root);
        int sum = 0;
        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;
    }

迭代都不难，懒得写Java版了

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前题目：代码随想录算法训练营第三期day17-二叉树04-创新互联
路径分享：http://cdkjz.cn/article/gdigs.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
成都柴油发电机租用主动防护网梓潼网站建设保温橡塑管时嘉做网站研帮主子晨木包装箱云锦斋建筑成都圣月服饰成都广告安装公司

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图