Iterative In-order traversal: In this method, we simulate the function call stack of the recursive in-order traversal using a stack data structure. It involves traversing the left subtree first, then visiting the current node, and finally, traversing the right subtree.
Iterative Pre-order traversal: In this approach, we use a stack to mimic the recursive pre-order traversal. It involves visiting the current node, then traversing the left subtree, and finally, traversing the right subtree.
Iterative Post-order traversal: This method can be a bit more complex than the other two. It requires two stacks or a single stack with additional bookkeeping to simulate the recursive post-order traversal. The nodes are processed in the order of the left subtree, right subtree, and then the current node.
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左 class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null){ return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if (node.right != null){ stack.push(node.right); } if (node.left != null){ stack.push(node.left); } } return result; } }
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右 class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null){ return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if (cur != null){ // Continuing the traversal of the left nodes stack.push(cur); cur = cur.left; }else{ // reached the end of the root node // add value into the result cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果 class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null){ return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()){ TreeNode node = stack.pop(); result.add(node.val); if (node.left != null){ stack.push(node.left); } if (node.right != null){ stack.push(node.right); } } Collections.reverse(result); return result; } }
Level-order traversal
先搞个que，把root加到que里面
while（que的长度不为0）
记录下que的长度，这就是这一排的元素个数
挨着把que的元素加到res里面去，加进去一个的同时把这个节点的子节点加入到que里面去。
implement breadth-first traversal (level-order traversal) of a binary tree using a queue.
//BFS--迭代方式--借助队列 public void checkFun02(TreeNode node) { if (node == null) return; Queue<TreeNode> que = new LinkedList<TreeNode>(); //!!! que.offer(node);
while (!que.isEmpty()) { //!!!! // new level List<Integer> itemList = new ArrayList<Integer>(); //!!!! int len = que.size();
while (len > 0) { TreeNode tmpNode = que.poll(); itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left); if (tmpNode.right != null) que.offer(tmpNode.right); len--; }
class Solution { public List<List<Integer>> res = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(TreeNode root) { trav(root); return res; } public void trav(TreeNode node){ if(node == null) return; Queue<TreeNode> que = new LinkedList<TreeNode>(); // !!!LinkedList, cant be arraylist que.offer(node); while(!que.isEmpty()){ //que != null int num = que.size(); // not length num用来记录每一排有几个元素 List<Integer> itemList = new ArrayList<Integer>(); //itemList 用来记录que里面马上要出来的一排的nodes while(num != 0){ TreeNode popNode = que.poll(); itemList.add(popNode.val); //准备好itemlist num--; if(popNode.left != null){ //把poll出去的节点的子节点offer进来 que.offer(popNode.left); } if(popNode.right != null){ que.offer(popNode.right); } }
//把itemList给加到res里面 res.add(itemList); }
} }
que==null VS. que.isEmpty()
que.isEmpty(): This is a method used to check if the queue is empty or not. The isEmpty() method is available in the java.util.Queue interface and is implemented by classes like LinkedList or PriorityQueue. It returns true if the queue has no elements, and false otherwise.
public class QueueExample { public static void main(String[] args) { Queue<String> queue = new LinkedList<>();
// Adding elements to the queue queue.offer("Element 1"); queue.offer("Element 2");
// Check if the queue is empty if (queue.isEmpty()) { System.out.println("Queue is empty."); } else { System.out.println("Queue is not empty."); } } }
que == null: This is a comparison that checks whether the reference que points to a valid queue object (i.e., not null). If que is a valid reference to a queue object, the comparison que == null will return false. If que is not pointing to any object (i.e., it is null), then the comparison will return true.
Here’s an example of how to use the que == null comparison:
public class QueueExample { public static void main(String[] args) { Queue<String> queue = null;
// Check if the queue reference is null if (queue == null) { System.out.println("Queue reference is null."); } else { System.out.println("Queue reference is not null."); } } }
In this example, we initialize the queue variable to null and then use the que == null comparison to check if the reference is null.
Remember that isEmpty() is used to check if the queue has no elements, while que == null is used to check if the reference to the queue object is null.
LinkedList
Initialization: To create an ArrayList, you can use the following syntax:
1 2
ArrayList<Type> listName = new ArrayList<Type>();
For example:
1 2
ArrayList<Integer> numbers = new ArrayList<Integer>();
Adding Elements: You can add elements to an ArrayList using the add method:
1 2
numbers.add(10); numbers.add(20);
Accessing Elements: You can access elements by their index using the get method:
1 2
int element = numbers.get(0); // Retrieves the first element
Removing Elements: You can remove elements by index or by value using the remove method:
1 2
numbers.remove(0); // Removes the first element numbers.remove(Integer.valueOf(20)); // Removes the first occurrence of the value 20
Checking Size: You can find the size (number of elements) in an ArrayList using the size method:
1 2
int size = numbers.size();
Checking if Empty: You can check if an ArrayList is empty using the isEmpty method:
1 2
boolean isEmpty = numbers.isEmpty();
Iterating: You can iterate through the elements of an ArrayList using various loops, such as for-each:
1 2 3
for (Integer number : numbers) { System.out.println(number); }
Clearing: You can remove all elements from an ArrayList using the clear method:
1 2
numbers.clear();
Checking for Existence: You can check if an element exists in the ArrayList using the contains method:
1 2
boolean contains = numbers.contains(10);
Converting to an Array: You can convert an ArrayList to an array using the toArray method:
class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> res = new ArrayList<Double>(); if(root == null) return res; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.add(root); while(!que.isEmpty()){ int num = que.size(); double mark = num; double sum = 0; while ( num != 0){ TreeNode temp = que.poll(); sum += temp.val; num--; if(temp.left != null) que.add(temp.left); if(temp.right != null) que.add(temp.right); } res.add(sum/mark);
public List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> levelOrder(Node root) { if(root == null) return res; Queue<Node> que = new LinkedList<Node>(); que.add(root); while(!que.isEmpty()){ int num = que.size(); List<Integer> list = new ArrayList<Integer>(); while(num > 0){ Node temp = que.poll(); list.add(temp.val); for(Node child: temp.children){ //!!! que.add(child); } num--; } res.add(list); }
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example 1:
1 2 3
Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1;
WAY2: 层序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Solution { public int layer = 0; public int maxDepth(TreeNode root) { if(root == null) return 0; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.add(root); while(!que.isEmpty()){ int num = que.size(); layer++; while(num != 0){ TreeNode temp = que.poll(); num --; if(temp.left!=null)que.add(temp.left); if(temp.right!=null)que.add(temp.right); } } return layer; } }
WAY3: pre-order traversal:(COMPLICATED, SO HAVENT READ)
class Solution { public int maxDepth(Node root) { if(root == null) return 0; int max = 0; for(Node child: root.children){ max = Math.max(max, maxDepth(child)); } return max+1; } }
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
1 2
Input: root = [1,2,3,4,5,6] Output: 6
递归遍历的顺序依然是后序（左右中）:
1 2 3 4 5 6 7 8
class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int left = countNodes(root.left) ; int right = countNodes(root.right) ; return left + right + 1; } }
int left = countNodes(root.left)+1 ;
int right = countNodes(root.right)+1 ;
return left + right;
这样的话，相当于上一层的那个节点被加了两次。
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
However, there are a few issues with the provided code:
The recursive calls to isBalanced inside the if condition are not returning the result. Instead, they are being called, but the result is not being used or returned.
The calculation of height in the methods countLef and countRig seems incorrect, as it simply returns the count of nodes in the left and right subtrees, respectively, rather than the height of the subtrees.
// class Solution { // public boolean isBalanced(TreeNode root) { // if(root == null) return true;
// if(countLef(root) - countRig(root) <= 1) { // isBalanced(root.left); // isBalanced(root.right); // }else{ // return false; // } // return true; // } // public int countLef(TreeNode node){ // if(node == null) return 0; // int left = countLef(node.left); // return left + 1; // } // public int countRig(TreeNode node){ // if(node == null) return 0; // int right = countRig(node.right); // return right + 1; // }
// }
class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; }
int leftHeight = height(root.left); int rightHeight = height(root.right);
if (Math.abs(leftHeight - rightHeight) <= 1) { // Check if both left and right subtrees are balanced return isBalanced(root.left) && isBalanced(root.right); !!!!!!!!!!!! } else { return false; } }
public int height(TreeNode node) { if (node == null) { return 0; }
// Compute the height of the left and right subtrees int leftHeight = height(node.left); int rightHeight = height(node.right);
// Return the maximum height plus 1 (to account for the current node) return Math.max(leftHeight, rightHeight) + 1; } }
public List<String> binaryTreePaths(TreeNode root) { deal(root, ""); return result; }
public void deal(TreeNode node, String s) { if (node == null) return; if (node.left == null && node.right == null) { result.add(new StringBuilder(s).append(node.val).toString()); //toString method converts StringBuider into String type. return; } String tmp = new StringBuilder(s).append(node.val).append("->").toString(); deal(node.left, tmp); deal(node.right, tmp); } }
//second try: class Solution { public List<String> res = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { if(root == null) return res; findPath(root, String.valueOf(root.val)); return res;
} public void findPath(TreeNode node, String path){ // if(node == null){ // res.add(path); // return; // } //!!!!!!!!!!notice where went wrong
if (node.left == null && node.right == null) { // Leaf node, add the path to the result res.add(path); return; } if(node.left != null){ findPath(node.left, path+ "->" + node.left.val); } if(node.right != null){ findPath(node.right, path+ "->" + node.right.val); } } }
class Solution { public int res = 0; public int maxDep = -1; // not 0 public int findBottomLeftValue(TreeNode root) { if(root == null) return 0; findLeft(root, 0); return res; } public void findLeft(TreeNode node, int depth){ if(node == null) return; if(node.left == null && node.right == null){
if(depth > maxDep){ maxDep = depth; res = node.val; } } depth++; if (node.left != null)findLeft(node.left,depth + 1); // 隐藏着回溯 if (node.right != null)findLeft(node.right,depth + 1); //notice not depth++ } }
class Solution { int res = 0; int maxdepth = -1; public int findBottomLeftValue(TreeNode root) { find(root,0); return res; } public void find(TreeNode root, int depth){ if(root == null) return; if(root.left == null && root.right == null){ if(depth > maxdepth){ res = root.val; maxdepth = depth; } } if(root.left != null){ depth ++; find(root.left, depth); depth--; } if(root.right != null){ depth ++; find(root.right, depth); depth--; }
} }
iterative method: (my version) // find the first node in the last row of the tree class Solution { public int res; public int findBottomLeftValue(TreeNode root) { if(root == null) return 0; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.add(root); while(! que.isEmpty()){ int num = que.size(); for(int i = 0; i < num; i++){ TreeNode temp = que.poll(); if(i == 0) res = temp.val; if(temp.left != null) que.add(temp.left); if(temp.right != null) que.add(temp.right); } } return res; }
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
1 2 3
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
class Solution { public boolean res = false; public boolean hasPathSum(TreeNode root, int targetSum) { check(root, targetSum, 0); return res; } public void check(TreeNode node, int targetSum, int sum){ if(node == null) return; sum += node.val; if(node.left == null && node.right == null){ if(targetSum == sum) res = true; }else{ check(node.left, targetSum, sum); check(node.right, targetSum, sum); } } }
// second try: time out class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { return count(root, targetSum, 0); } public boolean count(TreeNode node, int target, int sum){ if(node == null) return false; if(node.left == null && node.right == null) { //leaf sum += node.val; if(sum == target) return true; else return false; }
if(node.left != null) count(node.left, target, sum + node.val); if(node.right != null) count(node.right, target, sum + node.val); //return false; this is wrong !!!!!!!!!!!!! //In the provided code, the return false; statement is placed at the end of the count method. This statement will always be executed regardless of the conditions above it. return count(node.left, target, sum + node.val) || count(node.right, target, sum + node.val); } }
// modify: //1: class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { return count(root, targetSum, 0); } public boolean count(TreeNode node, int target, int sum){ if(node == null) return false; if(node.left == null && node.right == null) { //leaf sum += node.val; if(sum == target) return true; else return false; } boolean left = false; boolean right = false; if(node.left != null) left = count(node.left, target, sum + node.val); //!!!!!!!!!!! if(node.right != null) right = count(node.right, target, sum + node.val);//!!!!!!!!!!!!! return left || right; } }
//2: class Solution { public boolean res = false; public boolean hasPathSum(TreeNode root, int targetSum) { count(root, targetSum, 0); return res; } public void count(TreeNode node, int target, int sum){ //!!!!!!!!!! void if(node == null) return; if(node.left == null && node.right == null) { //leaf sum += node.val; if(sum == target) res = true; }
if(node.left != null) count(node.left, target, sum + node.val); if(node.right != null) count(node.right, target, sum + node.val); //return false; //return count(node.left, target, sum + node.val) || count(node.right, target, sum + node.val); } }
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length == 0 || inorder.length ==0) return null; return construct(preorder, 0, preorder.length, inorder, 0, inorder.length); } public TreeNode construct(int[] pre, int pres, int pree, int[]in, int ins, int ine){ if (pres == pree) return null; // Base case
int midValue = pre[pres]; TreeNode mid = new TreeNode(midValue); //mid.val = pre[pres]; if(pres - pree == 0) return mid; int index;
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the **subarray suffix ** to the right of the maximum value.
Return the maximum binary tree built fromnums.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12
Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1] Explanation: The recursive calls are as follow: - The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5]. - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1]. - Empty array, so no child. - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1]. - Empty array, so no child. - Only one element, so child is a node with value 1. - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is []. - Only one element, so child is a node with value 0. - Empty array, so no child.
Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.
Return the merged tree.
Note: The merging process must start from the root nodes of both trees.
实质上就是中序遍历 class Solution { public TreeNode max; public boolean isValidBST(TreeNode root) { if (root == null) return true; boolean left = isValidBST(root.left); //左 if(!left) return false;
if (max != null && root.val <= max.val) { //中 比较节点的逻辑 return false; } max = root; //记录当前节点的上一个节点，因为按照中序遍历，当前节点都应该比上一个节点大。
boolean right = isValidBST(root.right);//右 if(!right) return false;
return true; } }
// my class Solution { public TreeNode max; public boolean isValidBST(TreeNode root) { boolean left = true; boolean right = true; if(root.left != null) left = isValidBST(root.left); if(max!= null && root.val <= max.val){ return false; } max = root; if(root.right != null) right = isValidBST(root.right); return left && right;
mine: class Solution { public List<Integer> res = new ArrayList<Integer>(); public int min = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { if(root == null) return 0; inorder(root); check(res); return min; } public void inorder(TreeNode node){ if(node == null) return; inorder(node.left); res.add(node.val); inorder(node.right); } public void check(List<Integer> res){ for(int i = 0; i < res.size() - 1; i++){ int temp = res.get(i+1) - res.get(i); if(temp < min){ min = temp; } } } }
//SECOND TRY: class Solution { Integer pre; int dif = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { if(root == null) return dif; getMinimumDifference(root.left); if(pre != null ){ int temp = Math.abs(pre - root.val); if(dif > temp) dif = temp; } pre = root.val; getMinimumDifference(root.right); return dif; } }
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
1 2 3 4 5 6 7 8 9 10 11 12 13
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return null; if(root == p || root == q) return root; //网上返回 !!!!!!!!! TreeNode left = lowestCommonAncestor(root.left , p, q); TreeNode right = lowestCommonAncestor(root.right , p, q); if(left == null && right == null) return null; if(left == null && right != null) return right; if(left != null && right == null) return left; if(left != null && right != null) return root; //!!!!!!!!!!! return root; } }
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
1 2 3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example :
1 2 3
Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Example 1:
1 2 3 4 5
Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.
Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Given the root of a binary tree, flatten the tree into a “linked list”:
The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-ordertraversal of the binary tree.
