Chương 6: TREES - 3.Binary Trees: Problems & Solutions(13-26)

Problem-13

Đưa ra thuật toán tìm độ sâu nhỏ nhất của cây nhị phân.

Solution:

	public static int maxDepthLevelOrderTraversal(BinaryTreeNode root){
		if(root == null) {
			return 0;
		}
		
		Queue<BinaryTreeNode> q = new LinkedList<>();
		q.offer(root);
		q.offer(null);
		int count = 1;
		while(!q.isEmpty()) {
			BinaryTreeNode curr = q.poll();
			if(curr != null) {
                if(curr.left == null && curr.right == null){
                    return count;
                }
				if(curr.left != null) {
					q.offer(curr.left);
				}
				if(curr.right != null) {
					q.offer(curr.right);
				}
			} else {
				if(!q.isEmpty()) {
					count++;
					q.offer(null);
				}
			}
		}
		
		return count;
	}

Problem-14

Đưa ra thuật toán tìm nút sâu nhất của cây nhị phân.

Solution: Nút cuối cùng được xử lý từ hàng đợi theo thứ tự level là nút sâu nhất trong cây nhị phân.

	public BinaryTreeNode deepestNodeInBinaryTree(BinaryTreeNode root) {
		BinaryTreeNode tmp = null;
		if(root == null) {
			return null;
		}
		
		Queue<BinaryTreeNode> q = new LinkedList<>();
		q.offer(root);
		while(!q.isEmpty()) {
			tmp = q.poll();
			if(tmp.left != null) {
				q.offer(tmp.left);
			}
			if(tmp.right != null) {
				q.offer(tmp.right);
			}
		}
		
		return tmp;
	}

Problem-15

Đưa ra thuật toán xóa một phần tử (giả sử dữ liệu được cung cấp) khỏi cây nhị phân.

Solution: Việc xóa một node trong cây nhị phân có thể được thực hiện như sau:

• Bắt đầu từ gốc, tìm node mà chúng tôi muốn xóa.
• Tìm node sâu nhất trong cây.
• Thay thế dữ liệu của node sâu nhất bằng node sẽ bị xóa.
• Sau đó xóa node sâu nhất.

Problem-16

Đưa ra thuật toán tìm số lá trong cây nhị phân mà không cần sử dụng đệ quy.

Solution: Tập hợp các node có cả node trái và node phải là NULL được gọi là node lá.

	public static int numberOfLeavesInBTUsingLevelOrder(BinaryTreeNode root){
		int count = 0;
		if(root == null) {
			return 0;
		}
		
		Queue<BinaryTreeNode> q = new LinkedList<>();
		q.offer(root);
		while(!q.isEmpty()) {
			BinaryTreeNode tmp = q.poll();
			if(tmp.left == null && tmp.right == null) {
				count++;
			}
			if(tmp.left != null) {
				q.offer(tmp.left);
			}
			if(tmp.right != null) {
				q.offer(tmp.right);
			}
		}
		
		return count;
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-17

Đưa ra thuật toán tìm số lượng full node trong cây nhị phân mà không sử dụng đệ quy.

Solution: Tập hợp tất cả các node có cả node trái và node phải được gọi là full nodes.

	public static int numberOfFullNodeInBTUsingLevelOrder(BinaryTreeNode root){
		int count = 0;
		if(root == null) {
			return 0;
		}
		
		Queue<BinaryTreeNode> q = new LinkedList<>();
		q.offer(root);
		while(!q.isEmpty()) {
			BinaryTreeNode tmp = q.poll();
			if(tmp.left != null && tmp.right != null) {
				count++;
			}
			if(tmp.left != null) {
				q.offer(tmp.left);
			}
			if(tmp.right != null) {
				q.offer(tmp.right);
			}
		}
		
		return count;
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-18

Đưa ra thuật toán tìm số half node (các node chỉ có một node con) trong cây nhị phân mà không sử dụng đệ quy.

Solution: Tập hợp tất cả các node có con trái hoặc con phải (nhưng không phải cả hai) được gọi là half node.

	public static int numberOfHalfNodeInBTUsingLevelOrder(BinaryTreeNode root){
		int count = 0;
		if(root == null) {
			return 0;
		}
		
		Queue<BinaryTreeNode> q = new LinkedList<>();
		q.offer(root);
		while(!q.isEmpty()) {
			BinaryTreeNode tmp = q.poll();
			if((tmp.left != null && tmp.right == null) || (tmp.left == null && tmp.right != null)) {
				count++;
			}
			if(tmp.left != null) {
				q.offer(tmp.left);
			}
			if(tmp.right != null) {
				q.offer(tmp.right);
			}
		}
		
		return count;
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-19

Cho hai cây nhị phân, trả về true nếu chúng giống hệt nhau về mặt cấu trúc.

Solution: Algorithm:

• Nếu cả hai cây là NULL thì trả về true.
• Nếu cả hai cây không phải là NULL, thì kiểm tra đệ quy cấu trúc cây con bên trái và bên phải.

	public static boolean checkStructurllySameTrees(BinaryTreeNode root1, BinaryTreeNode root2) {
		if(root1 == null && root2 == null) {
			return true;
		}
		if(root1 == null || root2 == null) {
			return false;
		}
		return (checkStructurllySameTrees(root1.left, root2.left) && checkStructurllySameTrees(root1.right, root2.right));
	}

Time Complexity: O(n). Space Complexity: O(n), for recursive stack.

Problem-20

Đưa ra thuật toán tìm diameter(đường kính) của cây nhị phân. Diameter(Đường kính) của cây (đôi khi được gọi là width - chiều rộng) là số nút trên đường dẫn dài nhất giữa hai lá trong cây.

Solution: Để tìm đường kính của cây, trước tiên hãy tính đường kính của cây con bên trái và cây con bên phải theo cách đệ quy. Trong số hai giá trị này, chúng ta cần gửi giá trị tối đa cùng với mức hiện tại (+1).

	public static int deameterOfTree(BinaryTreeNode root) {
		int left, right;
		if(root == null) {
			return 0;
		}
		left = deameterOfTree(root.left);
		right = deameterOfTree(root.right);
		if(left + right > diameter) {
			diameter = left + right;
		}
		return Math.max(left, right) +1;
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-21

Đưa ra thuật toán tìm width(độ rộng) của cây nhị phân. Width của cây là số nút tối đa ở bất kỳ level (hoặc độ sâu-depth)) nào trong cây.

Solution:

	//The width of a binary tree is the maximum number of elements on one level of the tree
	public int width(BinaryTreeNode root) {
		int max = 0;
		int height = maxDepth(root);
		for(int k = 0; k <= height; k++) {
			int tmp = width(root, k);
			if(tmp > max) {
				max = tmp;
			}
		}
		return max;
	}
	
	//Returns the number of node on a given level
	public int width(BinaryTreeNode root, int depth) {
		if(root == null) {
			return 0;
		} else {
			if(depth == 0) {
				return 1;
			} else {
				return width(root.left, depth - 1) + width(root.right, depth - 1);
			}
		}
	}

Problem-22

Đưa ra thuật toán tìm level có tổng lớn nhất trong cây nhị phân.

Solution: Logic rất giống với việc tìm số các level. Thay đổi duy nhất là, chúng ta cũng cần theo dõi các tổng tương ứng.

	public int findLevelWithMaxSum(BinaryTreeNode root) {
		int maxSum = 0, currentSum = 0;
		if(root == null) {
			return 0;
		}
		// Initialization
		Queue<BinaryTreeNode> q  = new LinkedList<>();
		q.offer(root);
		q.offer(null);
		while(!q.isEmpty()) {
			BinaryTreeNode tmp = q.poll();
			if(tmp != null) {
				if(tmp.left != null) {
					q.offer(tmp.left);
				}
				if(tmp.right != null) {
					q.offer(tmp.right);
				}
				currentSum = currentSum + tmp.data;
			} else {
				if(currentSum > maxSum) {
					maxSum = currentSum;
				}
				currentSum = 0;
				//completion of a level
				if(!q.isEmpty()) {
					q.offer(null);
				}
			}
		}
		return maxSum;
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-23

Cho một cây nhị phân, hãy in ra tất cả các đường dẫn từ gốc đến lá của nó.

Solution:

	public void printPaths(BinaryTreeNode root) {
		int path[] = new int[256];
		printPaths(root, path, 0);
	}
	
	private void printPaths(BinaryTreeNode root, int[] path, int pathLen) {
		if(root == null) {
			return;
		}
		// append this node to the path array
		path[pathLen] = root.getData();
		pathLen++;
		// it's a leaf, so print the path that led to here
		if(root.left == null && root.right == null) {
			printArray(path, pathLen);
		} else {
			printPaths(root.left, path, pathLen);
			printPaths(root.right, path, pathLen);
		}
	}
	
	private void printArray(int[] ints, int len) {
		for(int i = 0; i < len; i++) {
			System.out.println(ints[i] + " ");
		}
	}

Time Complexity: O(n). Space Complexity: O(n), for recursive stack.

Problem-24

Đưa ra thuật toán kiểm tra sự tồn tại của đường đi với tổng cho trước. Điều này có nghĩa là, đưa ra một số cho trước, hãy kiểm tra xem có tồn tại đường dẫn từ gốc đến bất kỳ nút nào có tổng bằng số cho trước đó không.

Solution: Đối với vấn đề này, chiến lược là: trừ giá trị của node khỏi tổng trước khi gọi đệ quy các node con của nó và kiểm tra xem liệu tổng có bằng 0 khi chúng ta hết cây hay không.

	public boolean hasPathSum(BinaryTreeNode root, int sum) {
		if(root == null) {
			return false;
		}
		if(root.left == null && root.right == null && root.data == sum) {
			return true;
		} else {
			return hasPathSum(root.left, sum - root.data) || hasPathSum(root.right, sum - root.data);
		}
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-25

Đưa ra thuật toán tìm tổng các phần tử trong cây nhị phân.

Solution: Đệ quy, gọi tổng cây con bên trái, tổng cây con bên phải và thêm giá trị của chúng vào dữ liệu nút hiện tại.

	public int addBT(BinaryTreeNode root) {
		if(root == null) return 0;
		else {
			return (root.getData() + addBT(root.left) + addBT(root.right));
		}
	}

Time Complexity: O(n). Space Complexity: O(n).

Problem-26

Có thể xử lý Problem-25 mà không sử dụng đệ quy?

Solution: Chúng ta có thể sử dụng level order traversal với thay đổi đơn giản. Mỗi lần sau khi xóa một phần tử khỏi hàng đợi, hãy thêm giá trị dữ liệu của nút vào biến tổng.

	public int addBTWithoutRecursion(BinaryTreeNode root) {
		int sum = 0;
		if(root == null) {
			return 0;
		}
		Queue<BinaryTreeNode> q  = new LinkedList<>();
		q.offer(root);
		while(!q.isEmpty()) {
			BinaryTreeNode tmp = q.poll();
			sum = sum + tmp.data;
			if(tmp.left != null) {
				q.offer(tmp.left);
			}
			if(tmp.right != null) {
				q.offer(tmp.right);
			}
				
		}
		return sum;
	}

Time Complexity: O(n). Space Complexity: O(n).