JZ82 二叉樹中和為某一值的路徑(一)
代碼
package esay.JZ82二叉樹中和為某一值的路徑1;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
public class Solution {
/**
* 描述
* 給定一個二叉樹root和一個值 sum ，判斷是否有從根節點到葉子節點的節點值之和等于 sum 的路徑，
* 1.該題路徑定義為從樹的根結點開始往下一直到葉子結點所經過的結點
* 2.葉子節點是指沒有子節點的節點
* 3.路徑只能從父節點到子節點，不能從子節點到父節點
* 4.總節點數目為n
* 思路：
* 既然是檢查從根到葉子有沒有一條等于目標值的路徑，那肯定需要從根節點遍歷到葉子，我們可以在根節點每次往下一層的時候，將sum減去節點值，最后檢查是否完整等于0. 而遍歷的方法我們可以選取二叉樹常用的遞回前序遍歷，因為每次進入一個子節點，更新sum值以后，相當于對子樹查找有沒有等于新目標值的路徑，因此這就是子問題，遞回的三段式為：
* 終止條件： 每當遇到節點為空，意味著過了葉子節點，回傳，每當檢查到某個節點沒有子節點，它就是葉子節點，此時sum減去葉子節點值剛好為0，說明找到了路徑，
* 回傳值： 將子問題中是否有符合新目標值的路徑層層往上回傳，
*/
public boolean hasPathSum(TreeNode root, int sum) {
// write code here
if (root == null) return false;
if (root.left == null && root.right == null && sum - root.val == 0) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
/**
* 描述
* 求給定二叉樹的最大深度，
* 深度是指樹的根節點到任一葉子節點路徑上節點的數量，
* 最大深度是所有葉子節點的深度的最大值，
* （注：葉子節點是指沒有子節點的節點，）
* @param root
* @return
*/
public int maxDepth (TreeNode root) {
// write code here
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
// write code here
/**
* 思路：
* 要將一棵二叉樹的節點與另一棵二叉樹相加合并，肯定需要遍歷兩棵二叉樹，那我們可以考慮同步遍歷兩棵二叉樹，這樣就可以將每次遍歷到的值相加在一起，遍歷的方式有多種，這里推薦前序遞回遍歷，
* 集體做法
* step 1：首先判斷t1與t2是否為空，若為則用另一個代替，若都為空，回傳的值也是空，
* step 2：然后依據前序遍歷的特點，優先訪問根節點，將兩個根點的值相加創建到新樹中，
* step 3：兩棵樹再依次同步進入左子樹和右子樹，
*/
if (t1 == null || t2 == null) return t1 == null ? t2 : t1;
TreeNode treeNode = new TreeNode();
treeNode.val = t1.val + t2.val;
treeNode.left = mergeTrees(t1.left, t2.left);
treeNode.right = mergeTrees(t1.right, t2.right);
return treeNode;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/537986.html
標籤：Java