1.??minimum-depth-of-binary-tree

題目描述

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 求二叉樹的最小深度；

解題思路

遞歸遍歷二叉樹的每一個節點：

（1）如果該節點為null，返回深度為0；

（2）如果節點不為空，返回左，右孩子中較小的那個孩子的深度+1；

注意：在（2）中容易出現的問題是，如果一個節點只有左孩子，沒有右孩子，那么此時返回的應該是左孩子的深度，而不應該簡單的認為返回兩者的最小值；

1 public class Solution { 2 public int run(TreeNode root) { 3 if(root==null) 4 return 0; 5 int right = run(root.right); 6 int left = run(root.left); 7 return (left==0 || right==0)? (left+right+1) : Math.min(left,right)+1; 8 } 9 }

?

2.?binary-tree-postorder-traversal

題目描述

Given a binary tree, return the?postorder?traversal of its nodes' values.?后序遍歷二叉樹

For example:
Given binary tree{1,#,2,3},

1\2/3

return[3,2,1].

Note:?Recursive solution is trivial, could you do it iteratively?

解題思路：

后序遍歷的順序是：左->右->根，遞歸的方法很好寫：

1 public class Solution { 2 ArrayList<Integer> list = new ArrayList<Integer>(); 3 public ArrayList<Integer> postorderTraversal(TreeNode root) { 4 if(root==null) 5 return list; 6 if(root.left!=null) 7 postorderTraversal(root.left); 8 if(root.right!=null) 9 postorderTraversal(root.right); 10 list.add(root.val); 11 return list; 12 } 13 }

非遞歸方法，使用棧來迭代：

要保證根結點在左孩子和右孩子訪問之后才能訪問，因此對于任一結點P，先將其入棧。 （1）如果P不存在左孩子和右孩子，則可以直接訪問它； （2）或者P存在孩子，但是其孩子都已被訪問過了，則同樣可以直接訪問該結點 （3）若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了 注意：每次取棧頂元素的時候，左孩子在右孩子前面被訪問，左孩子和右孩子都在根結點前面被訪問。 1 public class Solution { 2 public ArrayList<Integer> postorderTraversal(TreeNode root) { 3 ArrayList<Integer> list = new ArrayList<Integer>(); 4 if(root==null) 5 return list; 6 Stack<TreeNode> S = new Stack<TreeNode>(); 7 TreeNode preNode = null; 8 S.push(root); 9 while(!S.isEmpty()){ 10 TreeNode curNode = S.peek(); 11 if((curNode.left==null && curNode.right==null)|| 12 (preNode != null && (preNode == curNode.left || preNode == curNode.right))){ 13 list.add(curNode.val); 14 S.pop(); 15 preNode = curNode; 16 } 17 else{ 18 if(curNode.right!=null) 19 S.push(curNode.right); 20 if(curNode.left!=null) 21 S.push(curNode.left); 22 } 23 } 24 return list; 25 } 26 }

?

3.?binary-tree-preorder-traversal

題目描述

Given a binary tree, return the?preorder?traversal of its nodes' values. 非遞歸前序遍歷二叉樹

For example:
Given binary tree{1,#,2,3},

1\2/3?

return[1,2,3].

Note:?Recursive solution is trivial, could you do it iteratively?

解題思路：

利用棧的結構，先序遍歷的順序為 根左右，根先進棧，每次從棧中彈出一個節點訪問，并把它的孩子（不為空）按先右后左的順序入棧，直到棧為空； 1 public class Solution { 2 public ArrayList<Integer> preorderTraversal(TreeNode root) { 3 Stack<TreeNode> S = new Stack<TreeNode>(); 4 ArrayList<Integer> list = new ArrayList<Integer>(); 5 if(root==null){ 6 return list; 7 } 8 S.push(root); 9 while(!S.isEmpty()){ 10 TreeNode tmp = S.pop(); 11 list.add(tmp.val); 12 if(tmp.right!=null) 13 S.push(tmp.right); 14 if(tmp.left!=null) 15 S.push(tmp.left); 16 } 17 return list; 18 } 19 }

?

4.?sum-root-to-leaf-numbers

題目描述

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

1/ \2 3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

從根節點到二叉樹的葉子節點的每一條路徑都有可以用一個數字表示，求這些數字的和；

解題思路：

用遞歸來做，主要就是考慮遞歸條件和結束條件。遞歸條件即是把當前的sum乘以10并且加上當前節點傳入下一函數，進行遞歸，最終把左右子樹的總和相加。結束條件的話就是如果一個節點是葉子，那么我們應該累加到結果總和中，如果節點到了空節點，則不是葉子節點，不需要加入到結果中，直接返回0即可。本質是一次先序遍歷。

1 public class Solution { 2 public int sumNumbers(TreeNode root) { 3 return Count(root, 0 ); 4 } 5 static int Count(TreeNode root,int sum){ 6 if(root==null) 7 return 0; 8 if(root.left==null&&root.right==null) 9 return sum*10+root.val; 10 return Count(root.left,sum*10+root.val)+Count(root.right,sum*10+root.val); 11 } 12 }

5.?binary-tree-maximum-path-sum

題目描述

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1/ \2 3

Return 6.

?找到二叉樹中和最大的一條路徑（任意節點為起點，不是根節點，不重復，不相交）

解題思路：

從根節點出發，遞歸地去找每個節點的左右子樹的最大和的路徑，返回當前節點的值+左右子樹中和較大的那個；

注意，遍歷每一條可能的路徑時，都要更新最大和是否小于當前這條路徑的和，是則更新；

1 public class Solution { 2 public int sum = Integer.MIN_VALUE; 3 public int maxPathSum(TreeNode root) { 4 if(root==null) 5 return 0; 6 max(root); 7 return sum; 8 } 9 public int max(TreeNode root){ 10 if(root==null) 11 return 0; 12 int left = Math.max(0, max(root.left)); 13 int right = Math.max(0, max(root.right)); 14 sum = Math.max(sum, left+right+root.val); 15 return Math.max(left, right)+root.val; 16 } 17 }

?6.?populating-next-right-pointers-in-each-node

題目描述

Given a binary tree

struct TreeLinkNode {TreeLinkNode *left;TreeLinkNode *right;TreeLinkNode *next;}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL.

Initially, all next pointers are set toNULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

1/ \2 3/ \ / \4 5 6 7

After calling your function, the tree should look like:

1 -> NULL/ \2 -> 3 -> NULL/ \ / \4->5->6->7 -> NULL

解題思路

由于是完全二叉樹，所以每一個節點如果有左孩子，一定有右孩子，所以左孩子的next指向右孩子，
右孩子的next指向其父節點next的左孩子（如果父節點不為空），如果父節點的next為空，則他也指向空；
所以，如果我們知道每一層最左邊的節點，那么就可以獲得下一層的第一個節點以及下一層所有節點的父節點； 1 public class Solution { 2 public void connect(TreeLinkNode root) { 3 if(root==null) 4 return; 5 root.next = null; 6 TreeLinkNode node = root, next = node; 7 while(node.left!=null){ 8 next = node; 9 while(next!=null){ 10 next.left.next = next.right; 11 if(next.next!=null) 12 next.right.next = next.next.left; 13 next = next.next; 14 } 15 node = node.left; 16 } 17 } 18 }

7.?populating-next-right-pointers-in-each-node-ii

題目描述

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

1/ \2 3/ \ \4 5 7

After calling your function, the tree should look like:

1 -> NULL/ \2 -> 3 -> NULL/ \ \4-> 5 -> 7 -> NULL

題目描述

與上題不同，給定的二叉樹不一定是完全二叉樹；
采用遞歸的方法，對于每一層，dummy指向每一層的第一個節點，對該層的每一個節點，處理它的孩子的next指向：
如果它有左孩子，那么prev的next就為當前節點的左孩子，并標記左孩子為prev；
如果它有右孩子，那么prev的next就為當前節點的右孩子，并標記右孩子為prev；
這樣，無論是否是完全二叉樹，都能實現next的正確指向。 1 public class Solution { 2 public void connect(TreeLinkNode root) { 3 if(root == null) 4 return; 5 TreeLinkNode dummy = new TreeLinkNode(-1); 6 TreeLinkNode cur; 7 TreeLinkNode prev = dummy; 8 for(cur=root; cur !=null; cur = cur.next){ 9 if(cur.left !=null) 10 { 11 prev.next = cur.left; 12 prev = prev.next; 13 } 14 if(cur.right !=null){ 15 prev.next = cur.right; 16 prev = prev.next; 17 } 18 } 19 connect(dummy.next); 20 } 21 }

8.?path-sum

題目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree andsum = 22, 5/ \4 8/ / \11 13 4/ \ \7 2 1

return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.

?解題思路

采用遞歸的思想：如果當前節點是葉子節點，且該節點的val等于sum，則返回true；

否則，遞歸第去判斷該節點的左子樹或者右子樹的和是否滿足sum-val。

1 public class Solution { 2 public boolean hasPathSum(TreeNode root, int sum) { 3 if(root==null) 4 return false; 5 if(root.left==null && root.right==null && root.val==sum) 6 return true; 7 return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); 8 } 9 }

9.?path-sum-ii

題目描述

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree andsum = 22, 5/ \4 8/ / \11 13 4/ \ / \7 2 5 1

return

[[5,4,11,2],[5,8,4,5] ]
找到路徑和為sum的所有路徑

?解題思路

判斷方法和上一題一樣，關鍵是路徑的存儲

1 public class Solution { 2 public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) { 3 ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); 4 if(root==null) 5 return list; 6 ArrayList<Integer> ls = new ArrayList<Integer>(); 7 find(list,ls,root,sum); 8 return list; 9 } 10 static void find(ArrayList<ArrayList<Integer>> list, ArrayList<Integer> ls, TreeNode root, int sum){ 11 if(root==null) 12 return; 13 ls.add(root.val); 14 if(root.left==null && root.right==null && root.val==sum){ 15 list.add(ls); 16 } 17 find(list,new ArrayList<Integer>(ls),root.left, sum-root.val); 18 find(list,new ArrayList<Integer>(ls),root.right, sum-root.val); 19 } 20 }

10.?balanced-binary-tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of?every?node never differ by more than 1.

解題思路

遞歸地判斷每顆子樹是否為高度平衡二叉樹（任一節點的左右子樹高度差不超過1）

1 public class Solution { 2 public boolean isBalanced(TreeNode root) { 3 if(root==null) 4 return true; 5 if(Math.abs(getDepth(root.left)-getDepth(root.right))>1) 6 return false; 7 return (isBalanced(root.left) && isBalanced(root.right)); 8 } 9 public int getDepth(TreeNode root){ 10 if(root==null) 11 return 0; 12 return 1+Math.max(getDepth(root.left),getDepth(root.right)); 13 } 14 }

?

?11.?binary-tree-level-order-traversal

題目描述

Given a binary tree, return the?level order?traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree{3,9,20,#,#,15,7},

3/ \9 20/ \15 7

return its level order traversal as:

[[3],[9,20],[15,7] ]

?解題思路

二叉樹的層次遍歷，用廣度優先搜索，采用隊列實現

1 import java.util.*; 2 public class Solution { 3 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { 4 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 5 if(root == null){ 6 return res; 7 } 8 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 9 queue.offer(root); 10 while(!queue.isEmpty()){ 11 ArrayList<Integer> arr = new ArrayList<Integer>(); 12 int size = queue.size(); 13 TreeNode p = queue.peek(); 14 for(int i=0;i<size;i++){ 15 if(queue.peek().left!=null) 16 queue.offer(queue.peek().left); 17 if(queue.peek().right!=null) 18 queue.offer(queue.peek().right); 19 arr.add(queue.poll().val); 20 } 21 res.add(arr); 22 } 23 return res; 24 } 25 }

12.?binary-tree-level-order-traversal-ii

解題思路

　　與上題類似，只不過每層的數據按從底向上輸出，仍然按照上題的方法遍歷二叉樹，但是每層的結果保存在一個棧中，最后按出棧順序保存在list里；

1 import java.util.*; 2 public class Solution { 3 public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) { 4 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 5 Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>(); 6 if(root==null) 7 return res; 8 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 9 queue.offer(root); 10 while(!queue.isEmpty()){ 11 ArrayList<Integer> arr = new ArrayList<Integer>(); 12 int size = queue.size(); 13 for(int i=0;i<size;i++){ 14 if(queue.peek().left!=null) 15 queue.offer(queue.peek().left); 16 if(queue.peek().right!=null) 17 queue.offer(queue.peek().right); 18 arr.add(queue.poll().val); 19 } 20 stack.push(arr); 21 } 22 while(!stack.isEmpty()){ 23 res.add(stack.pop()); 24 } 25 return res; 26 } 27 }

13.?binary-tree-zigzag-level-order-traversal

解題思路

Z字形層次遍歷二叉樹

與上題類似，添加一個標志，如果是偶數層，反轉該層的元素即可

1 import java.util.*;2 public class Solution {3 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {4 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();5 if(root == null){6 return res; 7 } 8 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 9 queue.offer(root); 10 boolean reserve = true; 11 while(!queue.isEmpty()){ 12 reserve = !reserve; 13 ArrayList<Integer> arr = new ArrayList<Integer>(); 14 int size = queue.size(); 15 TreeNode p = queue.peek(); 16 for(int i=0;i<size;i++){ 17 if(queue.peek().left!=null) 18 queue.offer(queue.peek().left); 19 if(queue.peek().right!=null) 20 queue.offer(queue.peek().right); 21 arr.add(queue.poll().val); 22 } 23 if(reserve){ 24 int len = arr.size(); 25 int t = len/2; 26 for(int i=0;i<t;i++){ 27 Collections.swap(arr,i,len-1-i); 28 } 29 } 30 res.add(arr); 31 } 32 return res; 33 } 34 }

14.?maximum-depth-of-binary-tree

解題思路

　　求二叉樹的最大深度

　　遞歸求左右子樹的最大深度，每個節點的最大深度為左右子樹的最大深度+1（自身）

1 public class Solution { 2 public int maxDepth(TreeNode root) { 3 return root == null ? 0 : (1 + Math.max(maxDepth(root.left), maxDepth(root.right))); 4 } 5 }

15.?symmetric-tree

給定一棵二叉樹，判斷其是否為對稱的二叉樹

解題思路

　　遞歸判斷左右子樹是否完全相同即可

1 public class Solution { 2 public boolean isSymmetric(TreeNode root) { 3 if(root==null) 4 return true; 5 return judge(root.left,root.right); 6 } 7 private static boolean judge(TreeNode a,TreeNode b){ 8 if(b==null && a==null) 9 return true; 10 else if((a==null && b!=null) || (a!=null && b==null)) 11 return false; 12 else 13 return (a.val==b.val && judge(a.left,b.right) && judge(a.right,b.left)); 14 } 15 }

16.?same-tree

判斷兩棵樹是否完全相同

解題思路

　　遞歸判斷兩個數的左子樹是否完全相同且右子樹完全相同

1 public class Solution { 2 public boolean isSameTree(TreeNode p, TreeNode q) { 3 if(p==null && q==null) 4 return true; 5 if( (p==null && q!=null) || (p!=null && q==null)) 6 return false; 7 return (p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)); 8 } 9 }

?

?

?

?

轉載于:https://www.cnblogs.com/PJQOOO/p/10978662.html

總結

以上是生活随笔為你收集整理的LeetCode 刷题笔记 （树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。