代碼隨想錄算法訓(xùn)練營(yíng)第三期day17-二叉樹(shù)04-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)致力于做網(wǎng)站、成都網(wǎng)站設(shè)計(jì),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化，推過(guò)標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。選擇創(chuàng)新互聯(lián)，就選擇了安全、穩(wěn)定、美觀(guān)的網(wǎng)站建設(shè)服務(wù)！

1、T110：平衡二叉樹(shù)

法1、遞歸

法2、迭代

2、T257：二叉樹(shù)的所有路徑

法1、遞歸

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

Ⅱ、版本2【分為隱式和顯式】

法2、迭代

3、T404：左葉子之和

法1、遞歸

法2、迭代（反正沒(méi)有順序要求，用隊(duì)列或棧都行）

Ⅰ、隊(duì)列層序遍歷（本人的本能）

Ⅱ、棧迭代

1、T110：平衡二叉樹(shù)

T110：給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。

本題中，一棵高度平衡二叉樹(shù)定義為：

一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)?的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 。

提示：

樹(shù)中的節(jié)點(diǎn)數(shù)在范圍?[0, 5000]?內(nèi)
-104?<= Node.val<= 104

S：

法1、遞歸

既然要求比較高度，理應(yīng)是要用后序遍歷

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);
        // 以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的大高度
    }

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);
        // 🚩用上一行就錯(cuò)！因?yàn)橛锌赡艹霈F(xiàn)leftHeight和rightHeight均為-1的情況
        return Math.abs(leftHeight - rightHeight) >1 ? -1 : 1 + Math.max(leftHeight, rightHeight); 
    }

法2、迭代

我們可以使用層序遍歷來(lái)求深度，但是就不能直接用層序遍歷來(lái)求高度了，這就體現(xiàn)出求高度和求深度的不同。

本題的迭代方式可以先定義一個(gè)函數(shù)，專(zhuān)門(mén)用來(lái)求高度。

這個(gè)函數(shù)通過(guò)棧模擬的后序遍歷找每一個(gè)節(jié)點(diǎn)的高度（其實(shí)是通過(guò)求傳入節(jié)點(diǎn)為根節(jié)點(diǎn)的大深度來(lái)求的高度）

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;
    }

此題用迭代法，其實(shí)效率很低，因?yàn)闆](méi)有很好的模擬回溯的過(guò)程，所以迭代法有很多重復(fù)的計(jì)算。

雖然理論上所有的遞歸都可以用迭代來(lái)實(shí)現(xiàn)，但是有的場(chǎng)景難度可能比較大。

2、T257：二叉樹(shù)的所有路徑

T257：給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn)?root?，按?任意順序?，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

葉子節(jié)點(diǎn)?是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

S：

這道題目要求從根節(jié)點(diǎn)到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節(jié)點(diǎn)指向孩子節(jié)點(diǎn)，找到對(duì)應(yīng)的路徑。

在這道題目中將第一次涉及到回溯，因?yàn)槲覀円崖窂接涗浵聛?lái)，需要回溯來(lái)回退一一個(gè)路徑在進(jìn)入另一個(gè)路徑。

法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();
            //最后一個(gè)不能再接箭頭
            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);
        }
    }

代碼精簡(jiǎn)了不少，也隱藏了不少東西。

在函數(shù)定義的時(shí)候 void traversal(TreeNode* cur, string path, vector& result)?，定義的是string path，每次都是復(fù)制賦值（~值傳遞），不用使用引用，否則就無(wú)法做到回溯的效果。

在上面的代碼中，貌似沒(méi)有看到回溯的邏輯，其實(shí)不然，回溯就隱藏在traversal(cur->left, path + "->", result);中的?path + "->"。?每次函數(shù)調(diào)用完，path依然是沒(méi)有加上"->" 的，這就是回溯了。

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);//🚩不會(huì)改變外面的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);🚩里面+=不會(huì)改變外面的path！
            path.pop_back();
            path.pop_back();
        }

    }

Java：不能用StringBuilder（如下，反正本人是用失敗了，畢竟數(shù)字不是一定只有一位的）

失敗版：

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);
        }
    }

通過(guò)版：

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);//該方法是左閉右開(kāi)區(qū)間
        }
        if (node.right != null) {
            path += "->";
            traversal(node.right, path, res);
            path = path.substring(0, path.length() - 2);
        }
    }

法2、迭代

除了模擬遞歸需要一個(gè)棧，同時(shí)還需要一個(gè)棧來(lái)存放對(duì)應(yīng)的遍歷路徑。

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();// 取出節(jié)點(diǎn) 中
            treeSt.pop();
            string path = pathSt.top();// 取出該節(jié)點(diǎn)對(duì)應(yīng)的路徑
            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;//不知為何用這兩行就不對(duì)
                // paths.push(path);
                nodes.push(node.left);
                paths.push(path + "->" + node.left.val);
            }
        }
        return res;
    }

如上所示，不知為何按照

3、T404：左葉子之和

T404：給定二叉樹(shù)的根節(jié)點(diǎn)?root?，返回所有左葉子之和。

提示:

節(jié)點(diǎn)數(shù)在?[1, 1000]?范圍內(nèi)
-1000<= Node.val<= 1000

S：

首先要清楚左葉子的定義：節(jié)點(diǎn)A的左孩子不為空，且左孩子的左右孩子都為空（說(shuō)明是葉子節(jié)點(diǎn)），那么A節(jié)點(diǎn)的左孩子為左葉子節(jié)點(diǎn)

法1、遞歸

遞歸的遍歷順序?yàn)楹笮颍ㄗ笥抑校?，因?yàn)橐ㄟ^(guò)遞歸函數(shù)的返回值來(lái)累加求取左葉子數(shù)值之和。

遇到左葉子節(jié)點(diǎn)的時(shí)候，記錄數(shù)值，然后遞歸求?左子樹(shù)左葉子之和，和右子樹(shù)左葉子之和，相加便是整個(gè)樹(shù)的左葉子之和。

C++：

int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int leftValue = sumOfLeftLeaves(root->left);// 左
        if (root->left && !root->left->left && !root->left->right) {// 左子樹(shù)就是一個(gè)左葉子的情況
            leftValue = root->left->val;//可能不理解為什么要替掉，也可以用midValue（見(jiàn)Java版）
        }
        int rightValue = sumOfLeftLeaves(root->right);// 右
        return leftValue + rightValue;// 中
    }

//->【精簡(jiǎn)版】
    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;//有沒(méi)有都行
        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、迭代（反正沒(méi)有順序要求，用隊(duì)列或棧都行） Ⅰ、隊(duì)列層序遍歷（本人的本能）

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);//如果按照后序，這兩行應(yīng)該上下對(duì)換（不過(guò)本題沒(méi)關(guān)系）
            if (node->right) st.push(node->right);
        }
        return sum;
    }

迭代都不難，懶得寫(xiě)Java版了

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱(chēng)：代碼隨想錄算法訓(xùn)練營(yíng)第三期day17-二叉樹(shù)04-創(chuàng)新互聯(lián)
文章源于：http://m.jiaotiyi.com/article/gdigs.html

網(wǎng)站建設(shè)知識(shí)

代碼隨想錄算法訓(xùn)練營(yíng)第三期day17-二叉樹(shù)04-創(chuàng)新互聯(lián)

其他資訊