代码随想录算法训练营第三期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://scyanting.com/article/gdigs.html