編程導(dǎo)航算法村第八關(guān) | 樹的深度優(yōu)先遍歷

判斷兩棵樹是否相同

• LeetCode100：給你兩棵二叉樹的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹是否相同。如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。
• 思路：
  • 兩課樹同時(shí)進(jìn)行前序遍歷，比較節(jié)點(diǎn)是否相等

public boolean isSameTree(TreeNode p, TreeNode q) {


        return preNode(p, q);

    }

    public boolean preNode(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        if (p!=null && q!=null && p.val != q.val) {
            return false;
        }
        return preNode(p.left, q.left) && preNode(p.right, q.right);
    }

對(duì)稱二叉樹

• LeetCode101 給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。
• 思路：
  • 兩顆樹同時(shí)進(jìn)行前序遍，root.left安裝前左右的順序遍歷、 root.right按照前右左的順序遍歷，比較節(jié)點(diǎn)是否相等

//  對(duì)稱二叉樹
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Boolean b = preNode(root.left, root.right);
        return b;
    }

    Boolean preNode(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }

        return preNode(left.left, right.right) && preNode(left.right, right.left);

    }

合并二叉樹

• LeetCode617.給定兩個(gè)二叉樹，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)，兩個(gè)二叉樹的一些節(jié)點(diǎn)便會(huì)重疊。你需要將他們合并為一個(gè)新的二叉樹。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)。
• 思路：
  • 對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行合并之后，還要對(duì)該節(jié)點(diǎn)的左右子樹分別進(jìn)行合并
  • 如果兩個(gè)節(jié)點(diǎn)非空，新節(jié)點(diǎn)就是兩個(gè)節(jié)點(diǎn)的和
  • 如果一個(gè)節(jié)點(diǎn)為空，則是另一個(gè)非空節(jié)點(diǎn)

//   合并到root1上
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if (root1 == null) {
            return root2;
        }

        if (root2 == null) {
            return root1;
        }

        TreeNode merge = new TreeNode(root1.val + root2.val);
        merge.left = mergeTrees(root1.left, root2.left);
        merge.right = mergeTrees(root1.right, root2.right);

        return merge;
    }

二叉樹的所有路徑

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

• 思路：
• 采用深度優(yōu)先遍歷
  • 找到葉子結(jié)點(diǎn)后，添加路徑到結(jié)果集中

 public List<String> binaryTreePaths(TreeNode root) {
        final ArrayList<String> result = new ArrayList<>();
        dfs(root, "", result);
        return result;
    }

    void dfs(TreeNode root, String path, List<String> res) {
        if (root==null){
            return;
        }


        path += root.val;
        if (root.left != null || root.right != null) {
            path += "->";
        }
        if (root!=null && root.left == null && root.right==null) {
            res.add(path);
        }

        dfs(root.left, path, res);
        dfs(root.right, path, res);
    }

路徑總和

上面我們討論的找所有路徑的方法，那我們是否可以再找一下哪條路徑的和為目標(biāo)值呢？這就是LeetCode112題：給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum ，判斷該樹中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum。葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-625782.html

• 思路:
  • 使用dfs算法，找出所有路徑的節(jié)點(diǎn)和，然后判斷目標(biāo)值是否在節(jié)點(diǎn)和列表中

public boolean hasPathSum(TreeNode root, int targetSum) {
        final ArrayList<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        if (result.contains(targetSum)) {
            return true;
        }
        return false;
    }

    void dfs(TreeNode root, int currentSum, List<Integer> result) {
        if (root == null) {
            return;
        }
        currentSum += root.val;
        if (root.left == null && root.right == null) {
            result.add(currentSum);
        }

        dfs(root.left, currentSum, result);
        dfs(root.right, currentSum, result);
    }

• 方法二：
  • 判斷targetSum是否存在的問題可以轉(zhuǎn)化為，判斷葉子結(jié)點(diǎn)的值是否等于targetSum-這條路徑上所有節(jié)點(diǎn)的和的問題
  • 左右子樹分別判斷

  public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        boolean left = hasPathSum(root.left, targetSum - root.val);
        boolean right = hasPathSum(root.right, targetSum - root.val);

        return left ||  right;
    }

二叉樹的反轉(zhuǎn)

• LeetCode226 翻轉(zhuǎn)二叉樹，將二叉樹整體反轉(zhuǎn)
• 思路：
  • 深度優(yōu)先算法：翻轉(zhuǎn)左右子樹

public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invertTree(root.left);
        invertTree(root.right);
        return root;

    }

到了這里，關(guān)于編程導(dǎo)航算法村第八關(guān) | 樹的深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！