1.Invert Binary Tree
Invert Binary Tree#即打印出二叉树的镜像
solution:root节点保持不变，左节点和右节点互换。然后分别左子树和右子进行invert(递归)
class Solution {
public TreeNode invertTree(TreeNode root) {
//recursion terminator
//current level processing
//dirll down
if (root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
2.判断二叉树是否镜像
[Symmetric Tree]https://leetcode.com/problems/symmetric-tree/description/
solution：递归，看代码
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && isMirror(p.left,q.right) && isMirror(p.right,q.left);
}
}
3.Valid Binary Search Tree
Valid Binary Search Tree
solution：递归，分别判断root.left ，root，root.right
class Solution {
public boolean isValidBST(TreeNode root) {
//利用stack & 中序遍历
//空树可以是任何树
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val <= pre.val) {
return false;
}
pre = root;
root = root.right;
}
return true;
}
}
4.二叉搜索树中第K小的元素
[Kth Smallest Element in a BST]https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
solution:因为左节点小于根节点小于右节点，二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式，我们就可以在找到第k小节点时马上退出。
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
}
5.二叉树的中序遍历
solution：利用stack
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
}
6.Maximum Depth of Binary Tree
solution：递归，左子树深度加上右子树的深度
class Solution {
public int maxDepth(TreeNode root) {
//递归
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1;
//注意Math.max()括号里面的写法
}
}
附上Minium Depth 题解，注意区别
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
if (root.left == null && root.right != null) {
return minDepth(root.right) + 1;
}
if (root.left != null && root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
}
}
7.Convert sorted list to Binary Search Tree
solution：快慢指针，当快指针走完的时候恰好慢指针走到中点，然后以中点为二叉树的根节点，左右两边进行递归
Convert sorted list to Binary Search Tree
class Solution {
public TreeNode sortedListToBST(ListNode head) {
//recurison
if (head == null) {
return null;
}
return toBST(head,null);
}
public TreeNode toBST(ListNode head,ListNode tail) {
ListNode slow = head;
ListNode fast = head;
if (head == tail) {
return null;
}
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode thead = new TreeNode(slow.val);
thead.left = toBST(head,slow);
thead.right = toBST(slow.next,tail);
return thead;
}
8.Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree
solution:找到中点，需要注意的是，数组变二叉树的函数toBST(nums,0,nums.length-1)，注意方法
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//recursion
if (nums == null) {
return null;
}
return toBST(nums, 0, nums.length - 1);
}
public TreeNode toBST(int[] nums, int start ,int end) {
if (start > end) {
return null;
}
TreeNode thead = new TreeNode(nums[(start + end) / 2]);
thead.left = toBST(nums, start, (start + end) / 2 - 1);
thead.right = toBST(nums, (start + end) / 2 + 1, end);
return thead;
}
}
9.Lowest Common Ancestor of a Binary Search Tree
Lowest Common Ancestor of a Binary Search Tree
solution : 递归，看代码理解
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}
10.Lowest Common Ancestor of a Binary Tree
[Lowest Common Ancestor of a Binary Tree]https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
solution：基本思路跟上一题一样，只不过这题是普通的二叉树，没法比较两个节点和根节点的大小关系。还是需要判断最近公共子节点是否出现在左右子树当中。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
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 root;
}
return left != null ? left : right;
}
}
11.判断另一个数的子树
[Subtree of Another Tree]https://leetcode.com/problems/subtree-of-another-tree/description/
solution：子树必须是从叶结点开始的，中间某个部分的不能算是子树，那么我们转换一下思路，是不是从s的某个结点开始，跟t的所有结构都一样，那么问题就转换成了判断两棵树是否相同，也就是Same Tree的问题了，这点想通了其实代码就很好写了，用递归来写十分的简洁，我们先从s的根结点开始，跟t比较，如果两棵树完全相同，那么返回true，否则就分别对s的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回true了，就表示可以找得到。
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
12.打印二叉树
剑指offer版本solution：每一次打印一个结点的时候，如果该结点有子结点， 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。
public static void printFromToBottom(BinaryTreeNode root) {
// 当结点非空时才进行操作
if (root != null) {
// 用于存放还未遍历的元素
Queue<BinaryTreeNode> list = new LinkedList<>();
// 将根结点入队
list.add(root);
// 用于记录当前处理的结点
BinaryTreeNode curNode;
// 队列非空则进行处理
while (!list.isEmpty()) {
// 删除队首元素
curNode = list.remove();
// 输出队首元素的值
System.out.print(curNode.value + " ");
// 如果左子结点不为空，则左子结点入队
if (curNode.left != null) {
list.add(curNode.left);
}
// 如果右子结点不为空，则左子结点入队
if (curNode.right != null) {
list.add(curNode.right);
}
}
}
}
13.把二叉树打印成多行
剑指offer版本solution：队列实现，宽度有限搜索，看注释
public static void print(BinaryTreeNode root) {
if (root == null) {
return;
}
List<BinaryTreeNode> list = new LinkedList<>();
BinaryTreeNode node;
// 当前层的结点个数
int current = 1;
// 记录下一层的结点个数
int next = 0;
list.add(root);
while (list.size() > 0) {
node = list.remove(0);
current--;
System.out.printf("%-3d", node.val);
if (node.left != null) {
list.add(node.left);
next++;
}
if (node.right != null) {
list.add(node.right);
next++;
}
if (current ==0) {
System.out.println();
current = next;
next = 0;
}
}
}
@两个队列实现
public void levelorder(TreeNode root) { // BFS
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
System.out.printf("Level %d\n", level++);
Queue<TreeNode> queue2 = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
System.out.printf("%d ", top.val);
if (top.left != null) queue2.offer(top.left);
if (top.right != null) queue2.offer(top.right);
}
queue = queue2;
}
}
14.将二叉树变为链表
solution：看代码
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}
15.恢复一个二叉搜索树
[Recover a Binary Search Tree]https://leetcode.com/problems/recover-binary-search-tree/description/
solution：解决方法是利用中序遍历找顺序不对的两个点，最后swap一下就好。
因为这中间的错误是两个点进行了交换，所以就是大的跑前面来了，小的跑后面去了。所以在中序便利时，遇见的第一个顺序为抵减的两个node，大的那个肯定就是要被recovery的其中之一，要记录。 另外一个，要遍历完整棵树，记录最后一个逆序的node。简单而言，第一个逆序点要记录，最后一个逆序点要记录，最后swap一下。
class Solution {
TreeNode pre;
TreeNode first;
TreeNode second;
public void recoverTree(TreeNode root) {
pre = null;
first = null;
second = null;
inorder(root);
if (first != null && second != null) {
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
public void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
if(pre == null) {
pre = root;//pre指针初始
} else {
if(pre.val > root.val) {
if ( first == null) {
first = pre;//第一个逆序点
}
second = root;//不断寻找最后一个逆序点
}
pre = root;
}
inorder(root.right);
}
}
16.计算一条从root节点到叶子节点的路径，这条路径的和等于某个常数
solution：分治，左子树路径找到一条等于sum - root.val，或者右子树找到一条路径和等于sum - root.val
[Path Sum]https://leetcode.com/problems/path-sum/description/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.val == sum && root.left == null && root.right == null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -root.val);
}
}
17.树的后续遍历
LeetCode版本solution：维护一个栈，往里面存入树的节点。维护一个列表，保存从栈出来的节点。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
//保存栈里弹出来的数
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}
18.二叉树的下一个节点
solution:(题意：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父节点的指针。)
如果一个结点有右子树，那么它的下一个结点就是它的右子树中的左子结点。也就是说右子结点出发一直沿着指向左子结点的指针，我们就能找到它的下一个结点。
接着我们分析一个结点没有右子树的情形。如果结点是它父节点的左子结点，那么它的下一个结点就是它的父结点。
如果一个结点既没有右子树，并且它还是它父结点的右子结点，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。
public static BinaryTreeNode getNext(BinaryTreeNode node) {
if (node == null) {
return null;
}
// 保存要查找的下一个节点
BinaryTreeNode target = null;
if (node.right != null) {
target = node.right;
while (target.left != null) {
target = target.left;
}
return target;
} else if (node.parent != null){
target = node.parent;
BinaryTreeNode cur = node;
// 如果父新结点不为空，并且，子结点不是父结点的左孩子
while (target != null && target.left != cur) {
cur = target;
target = target.parent;
}
return target;
}
return null;
}
网友评论