找樹左下角的值

題目鏈接：513. 找樹左下角的值

解題邏輯：

使用層序遍歷，將最后一層的第一個元素拿出來即可。

class Solution {public int findBottomLeftValue(TreeNode root) {Deque<List<Integer>> allItem = new LinkedList<>();Deque<TreeNode> que = new ArrayDeque<>();que.add(root);while(!que.isEmpty()) {List<Integer> row = new ArrayList<>();int count = que.size();while(count > 0) {TreeNode node = que.remove();count--;row.add(node.val);if(node.left != null) que.add(node.left);if(node.right != null) que.add(node.right);}allItem.add(row);}return allItem.removeLast().get(0);}
}

路徑總和

題目鏈接：112. 路徑總和

解題邏輯：

這個題可以當作257. 二叉樹的所有路徑這道題的延深，我們可以沿用此題的代碼，最后遍歷每條路徑上的和是否有符合條件的即可。

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null) return false;Deque<Integer> path = new ArrayDeque<>();List<Integer> allPathsAdd = new ArrayList<>();getAllPath(root,path,allPathsAdd);for(Integer sum : allPathsAdd) if(targetSum == sum) return true;return false;}public void getAllPath(TreeNode node,Deque<Integer> path,List<Integer> allPathsAdd){path.add(node.val);if(node.left == null && node.right == null) {int add =  0;for(Integer num : path) add += num;allPathsAdd.add(add);}if(node.left != null) {getAllPath(node.left,path,allPathsAdd);path.removeLast();}if(node.right != null) {getAllPath(node.right,path,allPathsAdd);path.removeLast();}}
}

上面的代碼是在257代碼的基礎上修改而來，這樣其實效率并不是很高，因為我們相當于是把所有路徑遍歷了出來，然后再檢驗是否存在符合條件的路徑，但其實我們在遍歷的途中發現有一條路徑已經符合條件了，那么就可以直接返回了，這樣就大大提升了效率。

修改后的代碼如下：

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null) return false;int count = 0;return getPathSum(root,count,targetSum);}public boolean getPathSum(TreeNode node,int count,int targetSum){count += node.val;if(node.left == null && node.right == null) {if(count == targetSum) return true;return false;}if(node.left != null) {boolean left = getPathSum(node.left,count,targetSum);if(left == true) return true;}if(node.right != null) {boolean right = getPathSum(node.right,count,targetSum);if(right == true) return true;}return false;}
}

總結：遞歸函數的返回值

遞歸函數什么時候需要返回值？什么時候不需要返回值？這里總結如下三點：

• 如果需要搜索整棵二叉樹且不用處理遞歸返回值，遞歸函數就不要返回值。（這種情況就是本文下半部分介紹的113.路徑總和ii）
• 如果需要搜索整棵二叉樹且需要處理遞歸返回值，遞歸函數就需要返回值。 （這種情況我們在236. 二叉樹的最近公共祖先 (opens new window)中介紹）
• 如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因為遇到符合條件的路徑了就要及時返回。（本題的情況）

路徑總和 II

題目鏈接：113. 路徑總和 II

與上一題的區別在于，本題要尋找所有符合條件的路徑，所以要遍歷整棵樹，并且我們對遞歸的返回值也不做處理，所以我們的遞歸方法可以不設置返回值。

代碼如下：

class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root == null) return new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();getPathSum(root,path,targetSum,result);return result;}public void getPathSum(TreeNode node,List<Integer> path,int targetSum,List<List<Integer>> result){path.add(node.val);if(node.left == null && node.right == null) {int count = 0;for(Integer num : path) count += num;if(count == targetSum) {List<Integer> deepCopy = new ArrayList<>();for (Integer obj : path) {deepCopy.add(obj); }result.add(deepCopy);   } return;}if(node.left != null) {getPathSum(node.left,path,targetSum,result);path.remove(path.size() - 1);}if(node.right != null) {getPathSum(node.right,path,targetSum,result);path.remove(path.size() - 1);}}
}

總結：二叉樹遞歸的思考

遍歷的選擇：看中的邏輯中需不需要左右的參與

遞歸，是遞和歸的兩個過程：

• 參數是在遞的過程中層層深入
• 返回值是在歸的過程中逐層向上返回
• 而回溯算法的邏輯就在歸的過程之后

從中序與后序遍歷序列構造二叉樹

題目鏈接：106. 從中序與后序遍歷序列構造二叉樹

解題邏輯：

首先要了解想要恢復一顆二叉樹，那么一定需要兩種遍歷方法，其中中序遍歷是一定需要的，而另一種遍歷方式可以是前序、后序、層序遍歷方式。

復原的原理如下圖所示：

本題是考察通過中序和后序構造二叉樹，其中后序遍歷是用來確定根節點的，而中序是用來確定根節點的左右子樹情況的。

本題選用后序遍歷的遞歸方式，這樣最后可以將左右子樹的根節點拼接到二叉樹的根節點左右。接下來從遞歸三部曲開始分析：

• 遞歸的參數與返回值：返回值為TreeNode，而參數為前序列表與后序列表，接下來將會對他遞歸切割
• 遞歸出口：當后序列表長度為0的時候，直接返回null。當后序列表的長度為1的時候，則直接根據這個值構建節點返回
• 遞歸單層邏輯：
  • 取到后序列表的最后一個元素，作為當前遞歸根節點
  • 在中序列表中找到該元素
  • 根據該元素對中序列表、后序列表進行切割
  • 左遞歸獲得左子節點
  • 右遞歸獲得右子節點
  • 將左右子節點組裝到根節點上
  • 返回根節點

代碼如下：

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length == 0) return null;if(postorder.length == 1) return new TreeNode(postorder[0]);int devideNum = postorder[postorder.length - 1];TreeNode root = new TreeNode(devideNum);int[] inorderLeft = Arrays.copyOfRange(inorder, 0, findNum(inorder,devideNum));int[] postorderLeft = Arrays.copyOfRange(postorder, 0, inorderLeft.length);root.left = buildTree(inorderLeft,postorderLeft);int[] inorderRight;if(findNum(inorder,devideNum) == inorder.length - 1) {inorderRight = new int[0];}else {inorderRight = Arrays.copyOfRange(inorder, findNum(inorder,devideNum) + 1,inorder.length);}int[] postorderRight = Arrays.copyOfRange(postorder, postorderLeft.length, postorder.length - 1);root.right = buildTree(inorderRight,postorderRight);return root;}public int findNum(int[] nums,int target){for(int i = 0;i < nums.length;i++) {if(nums[i] == target) return i;}return -1;}
}