LeetCode_easy_中文解析50題_day05

100、Same Tree

二十一、題目

給定兩個二叉樹，編寫一個函數來檢查它們是否相同。

如果兩個二叉樹在結構上相同并且節點具有相同的值，則認為它們是相同的。

思想：

遞歸思想，将問題拆成隻比較目前兩棵樹的這兩個節點，如果目前兩個節點都是空，那麼就傳回true，如果目前這兩個節點一個為空一個部位空，那肯定也不是相同的樹，如果兩個節點的val相同那就遞歸比較這兩個節點的左右子樹是否同上面說的那種情況，否則那就false，值不同那可定也不是相同的樹。

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
           

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
           

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false
           

package cn.hnu.leetcode.easy;

import cn.hnu.leetcode.easy.use_Class.TreeNode;

public class _100_IsSameTree {
	public boolean isSameTree(TreeNode p, TreeNode q) {
		
		//遞歸的思想
		//如果比較的兩棵樹的兩個目前節點都是空,那麼這兩棵樹相同
		if(p==null&&q==null){
			return true;
		}
		
		//如果比較的兩棵樹的兩個目前節點一個是空另一個不是空
		if(p==null&&q!=null||p!=null&&q==null){
			return false;
		}
		
		//如果當兩棵樹的目前節點都不為空,那就看它們的值是否相等,如果相等都走下面的if
		if(p.val==q.val){
			return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
		}
		
		//否則無論何種情況都是false
		return false;

	}
}
           

101、 Symmetric Tree

二十二、題目

給定一棵二叉樹，檢查它是否是自身成鏡像（即，是否中心對稱）。

思想：

同上題，先看看根節點是否為空，如果為空那麼直接傳回就是一個鏡像樹，否則應看它的左右子樹，如果左右子樹都為null傳回true，如果一個為空一個部位空，那麼傳回false；如果左子樹的val等于右子樹的val，

例如，這個二叉樹[1,2,2,3,4,3,3]是對稱的：

1
   / \
  2   2
 / \ / \
3  4 4  3
           

但是以下[1,2,2，null，3，null，3]不是：

1
   / \
  2   2
   \   \
   3    3
           

package cn.hnu.leetcode.easy;

import cn.hnu.leetcode.easy.use_Class.TreeNode;

public class _101_IsSymmetric {
	public boolean isSymmetric(TreeNode root) {
		
		//如果根節點是空 直接傳回就是鏡像樹
		if(root==null){
			return true;
		}
		
		
		//否則判斷它的左右子樹
		return isSymmetric(root.left,root.right);
		
	}
	
	private boolean isSymmetric(TreeNode left, TreeNode right) {
		
		//如果左右子樹都是空，傳回true
		if(left==null&&right==null){
			return true;
		}
		
		//如果左子樹為空，右子樹不為空，或者反過來。那麼傳回false
		if(left==null&&right!=null||(left!=null&&right==null)){
			return false;
		}
		
		//如果左子節點的val==右子節點的val 開始遞歸
		if(left.val==right.val){
			return isSymmetric(right.left, left.right)&&isSymmetric(right.right, left.left);
		}
		
		return false;
	}

}
           

104、Maximum Depth of Binary Tree

二十三、題目

給定二叉樹，找到它的最大深度。

最大深度是從根節點到最遠葉節點的最長路徑上的節點數。

注意：葉子是沒有子節點的節點。

思想：

同樣是遞歸，詳見代碼。

Example:

給定一棵樹

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

,

3
   / \
  9  20
    /  \
   15   7
           

傳回depth = 3.

package cn.hnu.leetcode.easy;

import cn.hnu.leetcode.easy.use_Class.TreeNode;

public class _104_MaxDepth {
	public int maxDepth(TreeNode root) {
		
		
		if(root==null){
			return 0;
		}
		
		int left = maxDepth(root.left);
		int right = maxDepth(root.right);
		
		return Math.max(left, right)+1;		
	}
}
           

107、Binary Tree Level Order Traversal II

二十四、題目

給定一棵二叉樹。自下而上，自左向右的順序輸出它每層的節點值。

思路：

先設定一個連結清單resultList用于存儲最終的結果，再設定一個隊列queue，用于存儲樹的每一個節點，就是一個将樹的節點放進隊列然後移除隊列首個位置放入一個levelList集合中，再将levelList中的元素放入到resultList的過程。期間還在不斷的向隊列中放入每個節點的左右子樹，直到周遊到葉子節點。

例如:

給定一棵二叉樹

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

,

3
   / \
  9  20
    /  \
   15   7
           

傳回結果如下:

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

package cn.hnu.leetcode.easy;

import java.util.LinkedList;
import java.util.List;

import cn.hnu.leetcode.easy.use_Class.TreeNode;

public class _107_LevelOrderBottom {
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		
		//建立一個雙向連結清單用于存儲最終的元素,它包含的元素也是一個一個list
		LinkedList<List<Integer>> resultList = new LinkedList<List<Integer>>();
		
		//建立一個list,其實也可以看成一個隊列,儲存每一個樹節點
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		
		//如果root為空,直接傳回初始化的空resultList即可
		if(root==null){
			return resultList;
		}
		
		//将根節點放入隊列中
		queue.offer(root);
		while(!queue.isEmpty()){
			
			int size = queue.size();
			LinkedList<Integer> levelList = new LinkedList<Integer>();
			for(int i = 0;i<size;i++){
				
				//擷取隊列的頭,但不删除
				//看它的左右子節點是否為空,不為空就添加進queue隊列中
				if(queue.peek().left!=null){
					queue.offer(queue.peek().left);
				}
				
				if(queue.peek().right!=null){
					queue.offer(queue.peek().right);
				}
				
				//然後是把目前隊列的頭添加進levelList
				levelList.add(queue.poll().val);
				
			}//end for
			
			//然後是将levelList添加進resultList的首位置
			//隊列不為空進入下一次的while循環
			resultList.add(0,levelList);
			
			
		}//end while
		//[[15,7],[9,20],[3]]
		return resultList;
	}
}
           

108、Convert Sorted Array to Binary Search Tree

二十五、題目

給定一個數組，其中數組中的元素按升序排列，将其轉換為平衡二叉樹。

平衡二叉樹：每個節點的兩個子樹的深度相差不超過1。

思路：

遞歸的思想，設定一個函數傳入數組，數組的起始位置low，和數組最後一個元素的索引high；每一次都将數組的中間元素作為根，然後數組的左半邊設定成根的左子樹，每個左邊的數組又遵循将其中間的設定成根，左邊的設定成左子樹；右子樹同左子樹，如此直到low>high的時候，遞歸結束。

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
           

package cn.hnu.leetcode.easy;

import cn.hnu.leetcode.easy.use_Class.TreeNode;

public class _108_SortedArrayToBST {

	public TreeNode sortedArrayToBST(int[] nums) {
		
		return binarySortTree(nums,0,nums.length-1);

	}

	//同樣采用遞歸的方式
	private TreeNode binarySortTree(int[] nums, int low, int high) {

		if(low>high){
			return null;
		}
		
		//每次都是給定數組範圍中間那個元素作為樹的根
		int mid = (low + high)/2;
		
		TreeNode node = new TreeNode(nums[mid]);
		
		//設定左節點
		node.left = binarySortTree(nums, low, mid-1);
		
		//設定右節點
		node.right = binarySortTree(nums, mid+1, high);
		
		return node;
		

		
	}

}