廣度優先搜尋(Breadth-first Search)
BFS在求解最短路徑或者最短步數上有很多的應用。應用最多的是在走迷宮上。
分析
樹的定義本身就是一種遞歸定義，是以對于樹相關的算法題，遞歸是最好的解決思路(在遞歸深度允許的情況下)。
遞歸版
public class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null||isMirror(root.left,root.right);
}
private boolean isMirror(TreeNode p,TreeNode q){
if(p==null&&q==null)
return true;
if(p==null||q==null)
return false;
if(p.val!=q.val)
return false;
return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
}
}
跌代版
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode left, right;
if(root.left!=null){
if(root.right==null) return false;
stack.push(root.left);
stack.push(root.right);
}
else if(root.right!=null){
return false;
}
while(!stack.empty()){
if(stack.size()%2!=0) return false;
right = stack.pop();
left = stack.pop();
if(right.val!=left.val) return false;
if(left.left!=null){//左子樹的左子樹和右子樹的右子樹比較
if(right.right==null) return false;
stack.push(left.left);
stack.push(right.right);
}
else if(right.right!=null){
return false;
}
if(left.right!=null){//左子樹的右子樹和右子樹的左子樹比較
if(right.left==null) return false;
stack.push(left.right);
stack.push(right.left);
}
else if(right.left!=null){
return false;
}
}
return true;
}
}
分析
層次周遊可以利用隊列實作。
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levels = new ArrayList<List<Integer>>();
if (root == null)
return levels;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);//記錄層次周遊的結果
if (node.left != null)
nextQueue.add(node.left);
if (node.right != null)
nextQueue.add(node.right);
}
queue = nextQueue;
levels.add(list);
}
return levels;
}
}
分析
與上一題的唯一差別：節點周遊的順序會交替變換，我們隻需要用一個變量标記每次周遊的順序即可。
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> levels = new LinkedList<List<Integer>>();
if (root == null)
return levels;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int mark = 0;//周遊方向的标記
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<Integer>();
Queue<TreeNode> nextqueue = new LinkedList<TreeNode>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null)
nextqueue.add(node.left);
if (node.right != null)
nextqueue.add(node.right);
}
queue = nextqueue;
if (mark == 1)//不同标記不同方向
Collections.reverse(list);
mark = (mark + 1) % 2;
levels.add(list);
}
return levels;
}
}
分析
與上上題的唯一差別：将結果集逆序。
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> levels=new ArrayList<List<Integer>>();
if(root==null)return levels;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
List<Integer> list=new ArrayList<Integer>();
Queue<TreeNode> nextQueue=new LinkedList<TreeNode>();
while(!queue.isEmpty()){
TreeNode node=queue.poll();
list.add(node.val);
if(node.left!=null)nextQueue.add(node.left);
if(node.right!=null)nextQueue.add(node.right);
}
queue=nextQueue;
levels.add(list);
}
Collections.reverse(levels);//将結果集逆序即可
return levels;
}
}
遞歸版
public class Solution {
public int minDepth(TreeNode root) {
if(root==null)return 0;
return doMinDepth(root);
}
public int doMinDepth(TreeNode root) {
if(root==null) return Integer.MAX_VALUE;
if(root.left==null&&root.right==null) return 1;
int leftDepth=doMinDepth(root.left);
int rightDepth=doMinDepth(root.right);
return 1+Math.min(leftDepth, rightDepth);
}
}
疊代版
利用後序周遊可以周遊所有從根節點的路徑。
public class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
Stack<TreeNode> stack=new Stack<TreeNode>();
Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>();
int min=Integer.MAX_VALUE;
TreeNode p=root;
while(p!=null||!stack.isEmpty()){//後續周遊
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.peek();
if(p.left==null&&p.right==null){
min=Math.min(min, stack.size());
}
if(p.right!=null){//具有右子樹
if(visit.get(p)==null){//第一次出現在棧頂
visit.put(p, true);
//處理右子樹
p=p.right;
}
else{//第二次出現在棧頂
stack.pop();
p=null; //右子樹已經處理過了
}
}else{
stack.pop();
p=null;
}
}
return min;
}
}
分析
初始化：location=0(<row=0,col=0>)。利用橫向優先搜尋算法，搜尋從location(<row,col>)出發所有連通的'O’。然後判定連通集合是否被包圍，如果被包圍則全部置為‘X’，否則全部标記為未被包圍。然後，從下一個可能被包圍的location開始繼續上述步驟，直到找不到下一個可能被包圍的location，算法結束。
public class Solution {
private void doSolve(char[][] board,HashSet<Integer> unSurrounded,int location){
int m=board.length,n=board[0].length;
while(location<m*n){//找到第一個可能被包圍的'O'
int r=location/n,c=location%n;
if(board[r][c]=='O'&&!unSurrounded.contains(location)){
break;
}
location++;
}
if(location==m*n)return;//處理完畢
//橫向優先搜尋
HashSet<Integer> founded=new HashSet<Integer>();//所有搜尋到的
HashSet<Integer> current=new HashSet<Integer>();//目前元素
founded.add(location);
current.add(location);
while(true){
HashSet<Integer> newLocations=new HashSet<Integer>();
for(Integer i:current){
int r=i/n,c=i%n;
//依次考慮上下左右的位置
if(r>0&&board[r-1][c]=='O'&&!founded.contains(i-n)){
founded.add(i-n);newLocations.add(i-n);}//上
if(r<m-1&&board[r+1][c]=='O'&&!founded.contains(i+n)){
founded.add(i+n);newLocations.add(i+n);}//下
if(c>0&&board[r][c-1]=='O'&&!founded.contains(i-1)){
founded.add(i-1);newLocations.add(i-1);}//左
if(c<n-1&&board[r][c+1]=='O'&&!founded.contains(i+1)){
founded.add(i+1);newLocations.add(i+1);}//右
}
if(newLocations.size()==0){
break;
}else{
current=newLocations;//隻有新增的位置，才能搜尋到新增位置
}
}
//檢查是否被包含
boolean surrounded=true;
for(Integer i:founded){
int r=i/n,c=i%n;
if(r==0||r==m-1||c==0||c==n-1){
surrounded=false;
break;
}
}
if(surrounded){
for(Integer i:founded){
int r=i/n,c=i%n;
board[r][c]='X';
}
}else{
for(Integer i:founded){
unSurrounded.add(i);
}
}
doSolve(board,unSurrounded,location);//遞歸求解
}
public void solve(char[][] board) {
if(board.length==0||board[0].length==0)return;
HashSet<Integer> unSurrounded=new HashSet<Integer>();//未被包圍的'O'
doSolve(board,unSurrounded,0);
}
}
分析
該問題等價于層次周遊過程中，每一層的末尾元素。
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
TreeNode last=null;//記錄每層末尾的元素
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
last=node;
if (node.left != null)
nextQueue.add(node.left);
if (node.right != null)
nextQueue.add(node.right);
}
queue = nextQueue;
res.add(last.val);
}
return res;
}
}
分析
依然是橫向優先搜尋，思路幾乎與上上題一緻。從location開始搜尋連通集合，然後将連通集合标記為已找到的island。然後，尋找下一個可能是island的location，繼續上述搜尋過程，直到找不到可能的island。
private int findIslands(char[][] grid,HashSet<Integer> islandLocation,int location){
int m=grid.length,n=grid[0].length;
while(location<m*n){//找到第一個可能是island的'1'
int r=location/n,c=location%n;
if(grid[r][c]=='1'&&!islandLocation.contains(location)){
break;
}
location++;
}
if(location==m*n) return 0;//處理完畢
//橫向優先搜尋
HashSet<Integer> founded=new HashSet<Integer>();//所有搜尋到的'1'
HashSet<Integer> current=new HashSet<Integer>();//目前元素
founded.add(location);
current.add(location);
while(true){
HashSet<Integer> newLocations=new HashSet<Integer>();
for(Integer i:current){
int r=i/n,c=i%n;
//依次考慮上下左右的位置
if(r>0&&grid[r-1][c]=='1'&&!founded.contains(i-n)){
founded.add(i-n);newLocations.add(i-n);}//上
if(r<m-1&&grid[r+1][c]=='1'&&!founded.contains(i+n)){
founded.add(i+n);newLocations.add(i+n);}//下
if(c>0&&grid[r][c-1]=='1'&&!founded.contains(i-1)){
founded.add(i-1);newLocations.add(i-1);}//左
if(c<n-1&&grid[r][c+1]=='1'&&!founded.contains(i+1)){
founded.add(i+1);newLocations.add(i+1);}//右
}
if(newLocations.size()==0){
break;
}else{
current=newLocations;//隻有新增的位置，才能搜尋到新增位置
}
}
for(Integer i:founded){//标記為island
islandLocation.add(i);
}
return 1+findIslands(grid,islandLocation,location);//遞歸求解
}
public int numIslands(char[][] grid) {
if(grid.length==0||grid[0].length==0)return 0;
HashSet<Integer> islandLocation=new HashSet<Integer>();
return findIslands(grid,islandLocation,0);
}
深度優先搜尋(Depth-first Search)
在我們遇到的一些問題當中，有些問題我們不能夠确切的找出數學模型，即找不出一種直接求解的方法，解決這一類問題，我們一般采用搜尋的方法解決。搜尋就是用問題的所有可能去試探，按照一定的順序、規則，不斷去試探，直到找到問題的解，試完了也沒有找到解，那就是無解，試探時一定要試探完所有的情況（實際上就是窮舉）；
深度優先搜尋（回溯法）作為最基本的搜尋算法，其采用了一種“一直向下走，走不通就掉頭”的思想（體會“回溯”二字），相當于采用了先根周遊的方法來構造搜尋樹。
分析
方案一：中序周遊
因為二叉查找數的中序周遊是遞增的，我們可以利用這個性質進行驗證。
public class Solution {
public boolean isValidBST(TreeNode root) {
//查找樹的中序周遊為遞增的
if(root==null)return true;
TreeNode pre=null;//上一個節點
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();
if(pre==null||pre.val<p.val){
pre=p;
}else{
return false;
}
if(p.right!=null){//處理右子樹
p=p.right;
}else{//處理上一層
p=null;
}
}
return true;
}
}
方案二：深度優先搜尋
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);//驗證樹中節點的值域
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;//檢查根節點的值是否在值域内
//根據根節點的值，限定子樹節點的值域
return isValidBST(root.left, minVal, root.val)
&& isValidBST(root.right, root.val, maxVal);
}
}
分析
方案一：中序周遊
假如，正常的中序周遊結果為1,2,3,4,5,6,7,8。交換後的中序周遊結果變成1,7,3,4,5,6,2,8，我們如何找到兩個颠倒位置的元素呢？
不難發現，重前往後第一個波峰，和從後往前第一個波谷。對于邊界，假定最左邊有個負無窮的元素，最右邊有個正無窮的元素。
空間複雜度為O(n)，時間複雜度為O(n)。
public class Solution {
public void recoverTree(TreeNode root) {
//查找樹的中序周遊為遞增,先擷取中序周遊，再定位交換位置
if(root==null)return ;
List<TreeNode> list=new ArrayList<TreeNode>();
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();
list.add(p);
if(p.right!=null){//處理右子樹
p=p.right;
}else{//處理上一層
p=null;
}
}
TreeNode firstNode=null;
TreeNode secondNode=null;
for(int i=0;i<list.size();i++){//從前往後找到第一個小大小
if(i==0){
if(list.get(i).val>list.get(i+1).val){
firstNode=list.get(i);
break;
}
}else{
if(list.get(i-1).val<list.get(i).val&&list.get(i).val>list.get(i+1).val){
firstNode=list.get(i);
break;
}
}
}
for(int i=list.size()-1;i>=0;i--){//從後往前找到第一個大小大
if(i==list.size()-1){
if(list.get(i-1).val>list.get(i).val){
secondNode=list.get(i);
break;
}
}else{
if(list.get(i-1).val>list.get(i).val&&list.get(i).val<list.get(i+1).val){
secondNode=list.get(i);
break;
}
}
}
int t=firstNode.val;firstNode.val=secondNode.val;secondNode.val=t;//交換
}
}
方案二
方案一的解決思路非常直覺，但是卻需要O(n)的空間複雜度。如果能在中序周遊過程中标記錯位的節點，空間複雜度就降為O(1)。
注：這裡所說的O(1)空間複雜度，應該不考慮疊代過程中的棧空間，特此說明。
見讨論區：https://discuss.leetcode.com/topic/2200/an-elegent-o-n-time-complexity-and-o-1-space-complexity-algorithm/2
public class Solution {
public void recoverTree(TreeNode root) {
//查找樹的中序周遊為遞增,先擷取中序周遊，再定位交換位置
if(root==null)return ;
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode firstNode=null;
TreeNode secondNode=null;
TreeNode p=root;
TreeNode preNode=null;//前驅
TreeNode prePreNode=null;//前驅的前驅
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();
if(preNode!=null){
//标記第一個小大小
if(firstNode==null&&preNode.val>p.val
&&(prePreNode==null||prePreNode.val<preNode.val)){
firstNode=preNode;
}
//标記最後一個大小大
if(prePreNode!=null){
if(prePreNode.val>preNode.val&&preNode.val<p.val){
secondNode=preNode;
}
}
if(p.right==null&&stack.isEmpty()){//最後一個節點特殊處理
if(preNode.val>p.val){
secondNode=p;
}
}
}
prePreNode=preNode;preNode=p;
if(p.right!=null){//處理右子樹
p=p.right;
}else{//處理上一層
p=null;
}//這裡為了闡述思路，其實可以簡化為 p=p.right;
}
int t=firstNode.val;firstNode.val=secondNode.val;secondNode.val=t;//交換
}
}
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null)
return true;
if(p==null||q==null)
return false;
return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
遞歸版
public class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null||isMirror(root.left,root.right);
}
private boolean isMirror(TreeNode p,TreeNode q){
if(p==null&&q==null)
return true;
if(p==null||q==null)
return false;
if(p.val!=q.val)
return false;
return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
}
}
跌代版
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode left, right;
if(root.left!=null){
if(root.right==null) return false;
stack.push(root.left);
stack.push(root.right);
}
else if(root.right!=null){
return false;
}
while(!stack.empty()){
if(stack.size()%2!=0) return false;
right = stack.pop();
left = stack.pop();
if(right.val!=left.val) return false;
if(left.left!=null){//左子樹的左子樹和右子樹的右子樹比較
if(right.right==null) return false;
stack.push(left.left);
stack.push(right.right);
}
else if(right.right!=null){
return false;
}
if(left.right!=null){//左子樹的右子樹和右子樹的左子樹比較
if(right.left==null) return false;
stack.push(left.right);
stack.push(right.left);
}
else if(right.left!=null){
return false;
}
}
return true;
}
}
分析
遞歸版
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
return doMaxDepth(root);
}
public int doMaxDepth(TreeNode root) {
if(root==null) return Integer.MIN_VALUE;
if(root.left==null&&root.right==null) return 1;
int leftDepth=doMaxDepth(root.left);
int rightDepth=doMaxDepth(root.right);
return 1+Math.max(leftDepth, rightDepth);
}
}
疊代版
二叉樹的後序周遊（深度優先周遊）可以通路到所有從根節點出發的路徑，我們隻需要在周遊過程中記錄最大深度即可。
public class Solution {
public int maxDepth(TreeNode root) {
Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); //标記節點通路情況
if(root==null) return 0;
int max=1;
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
max=Math.max(max, stack.size());//記錄最大深度
p=stack.peek();
if(p.right!=null){
if(visit.get(p)==null){
visit.put(p, true);
p=p.right;
}
else{
visit.remove(p);//移除
stack.pop();
p=null;
}
}else{
stack.pop();
p=null;
}
}
return max;
}
}
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n=preorder.length;
if(n==0)return null;
return doBuildTree(preorder,0,n-1,inorder,0,n-1);
}
public TreeNode doBuildTree(int[] preorder,int s1,int e1, int[] inorder,int s2,int e2){
if(e1<s1)return null;
int rootindex = 0;//根節點在中序序列中的位置
for(int i=s2;i<=e2;i++){
if(inorder[i]==preorder[s1]){
rootindex=i;
break;
}
}
int leftCount=rootindex-s2;//左子樹節點個數
TreeNode root=new TreeNode(preorder[s1]);
root.left=doBuildTree(preorder,s1+1,s1+leftCount,inorder,s2,rootindex-1);
root.right=doBuildTree(preorder,s1+leftCount+1,e1,inorder,rootindex+1,e2);
return root;
}
}
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n=inorder.length;
if(n==0)return null;
return doBuildTree(inorder,0,n-1,postorder,0,n-1);
}
public TreeNode doBuildTree(int[] inorder,int s1,int e1, int[] postorder,int s2,int e2){
if(e1<s1)return null;
int rootindex = 0;
for(int i=s1;i<=e1;i++){
if(inorder[i]==postorder[e2]){
rootindex=i;
break;
}
}
int leftCount=rootindex-s1;
TreeNode root=new TreeNode(postorder[e2]);
root.left=doBuildTree(inorder,s1,rootindex-1,postorder,s2,s2+leftCount-1);
root.right=doBuildTree(inorder,rootindex+1,e1,postorder,s2+leftCount,e2-1);
return root;
}
}
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int n=nums.length;
if(n==0)return null;
return doSortedArrayToBST(nums,0,n-1);
}
public TreeNode doSortedArrayToBST(int[] nums,int start,int end) {
if(end<start)return null;
int mid=(start+end)/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=doSortedArrayToBST(nums,start,mid-1);
root.right=doSortedArrayToBST(nums,mid+1,end);
return root;
}
}
分析
基本思路不變。隻是連結清單失去随機存取特性，尋找劃分點的時候需要線性查找。
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
ListNode p=head;
int n=0;
while(p!=null){
p=p.next;
n++;
}
return buildBST(head,n);
}
private TreeNode buildBST(ListNode head,int length){
if(length==0)return null;
TreeNode root=new TreeNode(-1);
if(length==1){
root.val=head.val;
return root;
}
int index=1;
int mid=(1+length)/2;
ListNode midNode=head;
while(index<mid){
midNode=midNode.next;
index++;
}
root.val=midNode.val;
root.left=buildBST(head,mid-1);
root.right=buildBST(midNode.next,length-mid);
return root;
}
}
public class Solution {
public boolean isBalanced(TreeNode root) {
return lengthOfTree(root)!=-1;
}
private int lengthOfTree(TreeNode root){
if(root==null) return 0;
int leftLength=lengthOfTree(root.left);
int rightLength=lengthOfTree(root.right);
if(leftLength==-1||rightLength==-1)return -1;
if(Math.abs(leftLength-rightLength)>1)return -1;
return Math.max(leftLength, rightLength)+1;
}
}
遞歸版
public class Solution {
public int minDepth(TreeNode root) {
if(root==null)return 0;
return doMinDepth(root);
}
public int doMinDepth(TreeNode root) {
if(root==null) return Integer.MAX_VALUE;
if(root.left==null&&root.right==null) return 1;
int leftDepth=doMinDepth(root.left);
int rightDepth=doMinDepth(root.right);
return 1+Math.min(leftDepth, rightDepth);
}
}
疊代版
public class Solution {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
Stack<TreeNode> stack=new Stack<TreeNode>();
Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>();
int min=Integer.MAX_VALUE;
TreeNode p=root;
while(p!=null||!stack.isEmpty()){//後續周遊
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.peek();
if(p.left==null&&p.right==null){
min=Math.min(min, stack.size());
}
if(p.right!=null){//具有右子樹
if(visit.get(p)==null){//第一次出現在棧頂
visit.put(p, true);
p=p.right;
}
else{//第二次出現在棧頂
visit.remove(p);
stack.pop();
p=null;
}
}else{
stack.pop();
p=null;
}
}
return min;
}
}
遞歸版
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
if(root.left==null&&root.right==null&&sum==root.val){
return true;
}
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
}
疊代版
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null){
return false;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>();
int min=Integer.MAX_VALUE;
TreeNode p=root;
int currentSum=0;
while(p!=null||!stack.isEmpty()){//後續周遊
while(p!=null){
currentSum+=p.val;
stack.push(p);
p=p.left;
}
p=stack.peek();
if(p.left==null&&p.right==null){
if(currentSum==sum)return true;
}
if(p.right!=null){//具有右子樹
if(visit.get(p)==null){//第一次出現在棧頂
visit.put(p, true);
p=p.right;
}
else{//第二次出現在棧頂
visit.remove(p);
stack.pop();
currentSum-=p.val;
p=null;
}
}else{
currentSum-=p.val;
stack.pop();
p=null;
}
}
return false;
}
}
遞歸版
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> paths = new ArrayList<>();
pathSumUtil(paths, new ArrayList<Integer>(), root, sum);
return paths;
}
private void pathSumUtil(List<List<Integer>> paths, List<Integer> currList, TreeNode root, int sum) {
if (root == null) {
return;
}
sum = sum - root.val;
currList.add(root.val);
if (sum == 0 && root.left == null && root.right == null) {
paths.add(new ArrayList<>(currList));//copy
}
pathSumUtil(paths, new ArrayList<>(currList), root.left, sum);
pathSumUtil(paths, new ArrayList<>(currList), root.right, sum);
}
}
疊代版
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
if(root==null) return res;
Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>();
Stack<TreeNode> stack=new Stack<TreeNode>();
int nowSum=0;
TreeNode p=root;
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
nowSum+=p.val;
p=p.left;
}
p=stack.peek();
if(p.left==null&&p.right==null&&sum==nowSum){
List<Integer> r=new ArrayList<Integer>();
for(Object i:stack.toArray())
r.add((Integer)((TreeNode)i).val);
res.add(r);
}
if(p.right!=null){
if(visit.get(p)==null){
visit.put(p, true);
//第一次處理右子樹
p=p.right;
}
else{
visit.remove(p);
nowSum-=p.val;
stack.pop();
p=null;
}
}else{
nowSum-=p.val;
stack.pop();
p=null;
}
}
return res;
}
}
分析
遞歸版
public class Solution {
public void flatten(TreeNode root) {
if (root == null)return;
doFlatten(root);
}
private TreeNode doFlatten(TreeNode root){//保證root!=null ，傳回尾部節點
if(root.left==null&&root.right==null)return root;
if(root.left==null){
TreeNode rightLast=doFlatten(root.right);
root.right=root.right;
root.left=null;
return rightLast;
}
if(root.right==null){
TreeNode leftLast=doFlatten(root.left);
root.right=root.left;
root.left=null;
return leftLast;
}
TreeNode leftLast=doFlatten(root.left);
TreeNode rightLast=doFlatten(root.right);
leftLast.right=root.right;
root.right=root.left;
root.left=null;
return rightLast;
}
}
疊代版
連結清單中的元素順序即為先序周遊後的順序。
public class Solution {
public void flatten(TreeNode root) {
if (root == null)return;
List<TreeNode> list=new ArrayList<TreeNode>();
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(p!=null||!stack.isEmpty()){
while(p!=null){
list.add(p);
stack.push(p);
p=p.left;
}
p=stack.pop();
p=p.right;
}
for(int i=0;i<list.size();i++){
TreeNode node=list.get(i);
node.left=null;
if(i==list.size()-1){
node.right=null;
}else{
node.right=list.get(i+1);
}
}
}
}
遞歸版
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)
return;
if(root.left!=null){
root.left.next=root.right;//将目前節點的左右子樹關聯
if(root.next != null)//将同一級别的相鄰樹關聯
root.right.next = root.next.left;
} <pre name="code" class="java"> connect(root.right);
connect(root.left); }}
疊代版
我們可以層次周遊樹，周遊過程中将同一級别的節點串聯起來。
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();
queue.add(root);
while(!queue.isEmpty()){
ArrayList<TreeLinkNode> list=new ArrayList<TreeLinkNode>(queue);
for(int i=0;i<list.size()-1;i++){//将同一級的節點串聯
list.get(i).next=list.get(i+1);
}
LinkedList<TreeLinkNode> nextQueue=new LinkedList<TreeLinkNode>();
while(!queue.isEmpty()){
TreeLinkNode node=queue.poll();
if(node.left!=null)nextQueue.add(node.left);
if(node.right!=null)nextQueue.add(node.right);
}
queue=nextQueue;
}
}
}
遞歸版
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null)
return;
//将目前節點的左右子樹關聯
if(root.left!=null){//
root.left.next=root.right;
}
//将同一級别的相鄰樹關聯
TreeLinkNode pre=root.right!=null?root.right:root.left;
TreeLinkNode nextTree=root.next;//相鄰樹
TreeLinkNode post=null;
while(nextTree!=null&&post==null){
post=nextTree.left!=null?nextTree.left:nextTree.right;
nextTree=nextTree.next;
}
if(pre!=null){
pre.next=post;
}
connect(root.right);//這裡的順序很關鍵
connect(root.left); //這裡的順序很關鍵
}
}
疊代版（與上一題相同）
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();
queue.add(root);
while(!queue.isEmpty()){
ArrayList<TreeLinkNode> list=new ArrayList<TreeLinkNode>(queue);
for(int i=0;i<list.size()-1;i++){//将同一級的節點串聯
list.get(i).next=list.get(i+1);
}
LinkedList<TreeLinkNode> nextQueue=new LinkedList<TreeLinkNode>();
while(!queue.isEmpty()){
TreeLinkNode node=queue.poll();
if(node.left!=null)nextQueue.add(node.left);
if(node.right!=null)nextQueue.add(node.right);
}
queue=nextQueue;
}
}
}
public class Solution {
public int maxPathSum(TreeNode root) {
List<Integer> res=doMaxPathSum(root);
return res.get(1);
}
//結果集中，第一個元素表示單向路徑最大和，第二個元素表示最大路徑和
public List<Integer> doMaxPathSum(TreeNode root){
List<Integer> res=new ArrayList<Integer>();
if(root==null){
res.add(Integer.MIN_VALUE);
res.add(Integer.MIN_VALUE);
return res;
}
List<Integer> leftRes=doMaxPathSum(root.left);
List<Integer> rightRes=doMaxPathSum(root.right);
int maxPath=root.val;
if(Math.max(leftRes.get(0),rightRes.get(0))>0) maxPath+=Math.max(leftRes.get(0),rightRes.get(0));
res.add(maxPath);
int maxSum=root.val;
if(leftRes.get(0)>0)maxSum+=leftRes.get(0);
if(rightRes.get(0)>0)maxSum+=rightRes.get(0);
res.add(Math.max(maxSum,Math.max(leftRes.get(1),rightRes.get(1))));
return res;
}
}
方案一
public class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int sum) {
if (root == null) return 0;
if (root.left == null && root.right == null)
return sum * 10 + root.val;
return dfs(root.left, sum * 10 + root.val) +
dfs(root.right, sum * 10 + root.val);
}
}