本文首發(fā)于我的個(gè)人博客：尾尾部落
0. 幾個(gè)概念
完全二叉樹：若二叉樹的高度是h掀抹，除第h層之外醋安，其他（1h-1）層的節(jié)點(diǎn)數(shù)都達(dá)到了最大個(gè)數(shù)谴轮，并且第h層的節(jié)點(diǎn)都連續(xù)的集中在最左邊池户。想到點(diǎn)什么沒片吊？實(shí)際上，完全二叉樹和堆聯(lián)系比較緊密哈~~
滿二叉樹：除最后一層外把还，每一層上的所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)实蓬，最后一層都是葉子節(jié)點(diǎn)。
哈夫曼樹：給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)吊履，構(gòu)造一棵二叉樹安皱，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹艇炎，也稱為哈夫曼樹(Huffman tree)酌伊。
二叉排序樹：又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹缀踪。二叉排序樹或者是一棵空樹居砖，或者是具有下列性質(zhì)的二叉樹：
- 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值驴娃；
- 若右子樹不空奏候，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
- 左唇敞、右子樹也分別為二叉排序樹蔗草；
- 沒有鍵值相等的節(jié)點(diǎn)
二分查找的時(shí)間復(fù)雜度是O(log(n))咒彤，最壞情況下的時(shí)間復(fù)雜度是O(n)（相當(dāng)于順序查找）
平衡二叉樹：又稱 AVL 樹。平衡二叉樹是二叉搜索樹的進(jìn)化版咒精，所謂平衡二叉樹指的是镶柱，左右兩個(gè)子樹的高度差的絕對值不超過 1。
紅黑樹：紅黑樹是每個(gè)節(jié)點(diǎn)都帶顏色的樹模叙，節(jié)點(diǎn)顏色或是紅色或是黑色歇拆，紅黑樹是一種查找樹。紅黑樹有一個(gè)重要的性質(zhì)向楼，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長的路徑不多于最短的路徑的長度的兩倍查吊。對于紅黑樹谐区，插入湖蜕，刪除，查找的復(fù)雜度都是O（log N）宋列。
1. 求二叉樹中的節(jié)點(diǎn)個(gè)數(shù)
遞歸解法：
（1）如果二叉樹為空昭抒，節(jié)點(diǎn)個(gè)數(shù)為0
（2）如果不為空，二叉樹節(jié)點(diǎn)個(gè)數(shù) = 左子樹節(jié)點(diǎn)個(gè)數(shù) + 右子樹節(jié)點(diǎn)個(gè)數(shù) + 1
參考代碼如下：
public static int getNodeNumRec(TreeNode root) {
if (root == null) {
return 0;
}
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}
2. 求二叉樹的最大層數(shù)(最大深度)
劍指offer：二叉樹的深度
遞歸解法：
（1）如果二叉樹為空炼杖，二叉樹的深度為0
（2）如果二叉樹不為空灭返，二叉樹的深度 = max(左子樹深度， 右子樹深度) + 1
參考代碼如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}
2.1 二叉樹的最小深度
LeetCode：Minimum Depth of Binary Tree
給定一個(gè)二叉樹坤邪，找出其最小深度熙含。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
class Solution {
public int minDepth(TreeNode root) {
if(root == null)
return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
}
3. 先序遍歷/前序遍歷
LeetCode：Binary Tree Preorder Traversal
給定二叉樹艇纺，返回其節(jié)點(diǎn)值的前序遍歷怎静。
根 - 左 - 右
遞歸
ArrayList<Integer> preOrderReverse(TreeNode root){
ArrayList<Integer> result = new ArrayList<Integer>();
preOrder(root, result);
return result;
}
void preOrder(TreeNode root,ArrayList<Integer> result){
if(root == null){
return;
}
result.add(root.val);
preOrder(root.left, result);
preOrder(root.right, result);
}
非遞歸
法一：
import java.util.Stack;
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
return res;
}
}
法二：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur!=null){
res.add(cur.val);
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
cur = cur.right;
}
}
return res;
}
}
4. 中序遍歷
LeetCode：Binary Tree Inorder Traversal
給定二叉樹，返回其節(jié)點(diǎn)值的中序遍歷黔衡。
左 - 根 - 右
遞歸
void inOrder(TreeNode root,ArrayList<Integer> result){
if(root == null){
return;
}
preOrder(root.left, result);
result.add(root.val);
preOrder(root.right, result);
}
非遞歸
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(!stack.isEmpty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
}
5. 后序遍歷
Leetcode：Binary Tree Postorder Traversal
給定二叉樹蚓聘，返回其節(jié)點(diǎn)值的后序遍歷。
左 - 右 - 根
遞歸
void inOrder(TreeNode root,ArrayList<Integer> result){
if(root == null){
return;
}
preOrder(root.left, result);
preOrder(root.right, result);
result.add(root.val);
}
非遞歸
方法一：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;
}
}
方法二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
TreeNode visited = null;
while(!stack.isEmpty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.peek();
if(cur.right != null && cur.right != visited){
cur = cur.right;
}else{
res.add(cur.val);
visited = cur;
stack.pop();
cur = null;
}
}
}
return res;
}
}
方法三(推薦)：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}
}
6. 分層遍歷
LeetCode：Binary Tree Level Order Traversal
劍指offer：從上往下打印二叉樹
劍指offer：把二叉樹打印成多行
給定二叉樹盟劫，返回其節(jié)點(diǎn)值的級別順序遍歷夜牡。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode cur = null;
queue.add(root);
while(!queue.isEmpty()){
ArrayList<Integer> level = new ArrayList<Integer>();
int l = queue.size();
for(int i=0; i<l;i++){
cur = queue.poll();
level.add(cur.val);
if(cur.left != null)
queue.add(cur.left);
if(cur.right != null)
queue.add(cur.right);
}
res.add(level);
}
return res;
}
}
6.1 自下而上分層遍歷
LeetCode：Binary Tree Level Order Traversal II
給定二叉樹，返回其節(jié)點(diǎn)值的自下而上級別順序遍歷侣签。
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null)
return res;
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> temp = new LinkedList<>();
for(int i=0; i<count; i++){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
}
// 每次都添加到第一個(gè)位置
res.add(0, temp);
}
return res;
}
}
6.2 按之字形順序打印二叉樹
劍指offer：按之字形順序打印二叉樹
請實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹塘装，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印影所，第三行按照從左到右的順序打印蹦肴，其他行以此類推。
設(shè)兩個(gè)棧型檀，s2存放奇數(shù)層冗尤，s1存放偶數(shù)層
遍歷s2節(jié)點(diǎn)的同時(shí)按照左子樹、右子樹的順序加入s1，
遍歷s1節(jié)點(diǎn)的同時(shí)按照右子樹裂七、左子樹的順序加入s2
import java.util.ArrayList;
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
int flag = 1;
if(pRoot == null)
return res;
s2.push(pRoot);
ArrayList<Integer> temp = new ArrayList<Integer>();
while(!s1.isEmpty() || !s2.isEmpty()){
if(flag % 2 != 0){
while(!s2.isEmpty()){
TreeNode node = s2.pop();
temp.add(node.val);
if(node.left != null){
s1.push(node.left);
}
if(node.right != null){
s1.push(node.right);
}
}
}
if(flag % 2 == 0){
while(!s1.isEmpty()){
TreeNode node = s1.pop();
temp.add(node.val);
if(node.right != null){
s2.push(node.right);
}
if(node.left != null){
s2.push(node.left);
}
}
}
res.add(new ArrayList<Integer>(temp));
temp.clear();
flag ++;
}
return res;
}
}
7. 求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)
void get_k_level_number(TreeNode root, int k){
if(root == null || k <=0){
return 0;
}
if(root != null && k == 1){
return 1;
}
return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1);
}
8. 求二叉樹第K層的葉子節(jié)點(diǎn)個(gè)數(shù)
void get_k_level_leaf_number(TreeNode root, int k){
if(root == null || k <=0){
return 0;
}
if(root != null && k == 1){
if(root.left == null && root.right == null)
return 1;
else
return 0;
}
return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1);
}
9. 判斷兩棵二叉樹是否結(jié)構(gòu)相同
LeetCode：Same Tree
給定兩個(gè)二叉樹皆看，編寫一個(gè)函數(shù)來檢查它們是否相同。
遞歸解法：
（1）如果兩棵二叉樹都為空背零，返回真
（2）如果兩棵二叉樹一棵為空腰吟，另一棵不為空，返回假
（3）如果兩棵二叉樹都不為空徙瓶，如果對應(yīng)的左子樹和右子樹都同構(gòu)返回真毛雇，其他返回假
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val == q.val)
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
return false;
}
}
10. 判斷二叉樹是不是平衡二叉樹
LeetCode：Balanced Binary Tree
給定二叉樹，確定它是否是高度平衡的侦镇。
對于此問題灵疮，高度平衡二叉樹定義為： 一個(gè)二叉樹，其中每個(gè)節(jié)點(diǎn)的兩個(gè)子樹的深度差不相差超過1壳繁。
遞歸解法：
（1）如果二叉樹為空震捣，返回真
（2）如果二叉樹不為空，如果左子樹和右子樹高度相差不大于1且左子樹和右子樹都是AVL樹闹炉，返回真蒿赢，其他返回假
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null)
return true;
return Math.abs(maxHigh(root.left) - maxHigh(root.right)) <= 1
&& isBalanced(root.left) && isBalanced(root.right);
}
public int maxHigh(TreeNode root){
if(root == null)
return 0;
return Math.max(maxHigh(root.left), maxHigh(root.right))+1;
}
}
11. 求二叉樹的鏡像
劍指offer：二叉樹的鏡像
LeetCode：Invert Binary Tree
反轉(zhuǎn)二叉樹
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return root;
TreeNode node = root.left;
root.left = invertTree(root.right);
root.right = invertTree(node);
return root;
}
}
11.1 對稱二叉樹
劍指offer：對稱的二叉樹
LeetCode：Symmetric Tree
給定一個(gè)二叉樹，檢查它是否是鏡像對稱的渣触。
image
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || isSymmetricHelper(root.left, root.right);
}
public boolean isSymmetricHelper(TreeNode left, TreeNode right){
if(left == null && right == null)
return true;
if(left == null || right == null)
return false;
if(left.val != right.val)
return false;
return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}
}
12. 求二叉樹中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)
LeetCode：Lowest Common Ancestor of a Binary Tree
給定二叉樹羡棵，找到樹中兩個(gè)給定節(jié)點(diǎn)的最低共同祖先（LCA）。
遞歸解法：
（1）如果兩個(gè)節(jié)點(diǎn)分別在根節(jié)點(diǎn)的左子樹和右子樹嗅钻，則返回根節(jié)點(diǎn)
（2）如果兩個(gè)節(jié)點(diǎn)都在左子樹皂冰，則遞歸處理左子樹；如果兩個(gè)節(jié)點(diǎn)都在右子樹啊犬，則遞歸處理右子樹
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || 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 ? right : left;
}
}
12.1 求二叉搜索樹的最近公共祖先
LeetCode：Lowest Common Ancestor of a Binary Search Tree
給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先灼擂。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q觉至，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x剔应，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）语御【”
注意二叉搜索樹的特性：
左子樹 < 根節(jié)點(diǎn) < 右子樹
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}
else if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}
else{
return root;
}
}
}
13. 求二叉樹的直徑
LeetCode：Diameter of Binary Tree
給定一棵二叉樹，你需要計(jì)算它的直徑長度应闯。一棵二叉樹的直徑長度是任意兩個(gè)結(jié)點(diǎn)路徑長度中的最大值纤控。這條路徑可能穿過根結(jié)點(diǎn)。
遞歸解法：對于每個(gè)節(jié)點(diǎn)碉纺，它的最長路徑等于左子樹的最長路徑+右子樹的最長路徑
class Solution {
private int path = 0;
public int diameterOfBinaryTree(TreeNode root) {
diamHelper(root);
return path;
}
private int diamHelper(TreeNode root){
if(root == null)
return 0;
int left = diamHelper(root.left);
int right = diamHelper(root.right);
path = Math.max(path, left + right);
return Math.max(left, right) + 1;
}
}
14. 由前序遍歷序列和中序遍歷序列重建二叉樹
劍指offer：重建二叉樹
LeetCode：Construct Binary Tree from Preorder and Inorder Traversal
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹船万。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0 || inorder.length == 0)
return null;
return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode buildTreeHelper(int[] preorder, int pre_start, int pre_end,
int[] inorder, int in_start, int in_end){
if(pre_start > pre_end || in_start > in_end)
return null;
TreeNode root = new TreeNode(preorder[pre_start]);
for(int i = in_start; i <= in_end; i++){
if(inorder[i] == preorder[pre_start]){
// 左子樹的長度：i-is
root.left = buildTreeHelper(preorder, pre_start + 1, pre_start + i - in_start, inorder, in_start, i - 1);
root.right = buildTreeHelper(preorder, pre_start + i - in_start + 1, pre_end, inorder, i + 1, in_end);
}
}
return root;
}
}
14.1 從中序與后序遍歷序列構(gòu)造二叉樹
LeetCode：Construct Binary Tree from Inorder and Postorder Traversal
根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹刻撒。
本題與“從前序與中序遍歷序列構(gòu)造二叉樹”是一個(gè)套路。唯一的區(qū)別是耿导，后序序列的最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)声怔，因此我們要從后序序列的最后一個(gè)節(jié)點(diǎn)入手，再去中序序列中找到這個(gè)節(jié)點(diǎn)舱呻。在這個(gè)節(jié)點(diǎn)左側(cè)的屬于根節(jié)點(diǎn)的左子樹部分醋火，右側(cè)的屬于根節(jié)點(diǎn)右子樹部分。然后根據(jù)左右子樹節(jié)點(diǎn)的數(shù)量箱吕，在后序序列中找到他們各自的后序序列芥驳。比左子樹節(jié)點(diǎn)個(gè)數(shù)為5，那么在后序序列中前五個(gè)節(jié)點(diǎn)就是左子樹節(jié)點(diǎn)茬高，之后的節(jié)點(diǎn)除了最后一個(gè)節(jié)點(diǎn)都是右子樹節(jié)點(diǎn)兆旬。
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0)
return null;
return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
public TreeNode buildTreeHelper(int[] inorder, int in_start, int in_end,
int[] postorder, int post_start, int post_end){
if(in_start > in_end || post_start > post_end)
return null;
TreeNode root = new TreeNode(postorder[post_end]);
for(int i = in_start; i <= in_end; i++){
if(inorder[i] == postorder[post_end]){
root.left = buildTreeHelper(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1);
root.right = buildTreeHelper(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1);
}
}
return root;
}
}
提示：根據(jù)前序和后序遍歷無法構(gòu)造出唯一的二叉樹
15. 判斷二叉樹是不是完全二叉樹
完全二叉樹是指最后一層左邊是滿的，右邊可能慢也不能不滿雅采，然后其余層都是滿的爵憎，根據(jù)這個(gè)特性慨亲，利用層遍歷婚瓜。如果我們當(dāng)前遍歷到了NULL結(jié)點(diǎn)，如果后續(xù)還有非NULL結(jié)點(diǎn)刑棵，說明是非完全二叉樹巴刻。
class Solution {
public boolean _CheckCompleteTree(TreeNode root) {
Queue<TreeNode> queue = LinkedList<>();
if(root == null)
return true;
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.pop();
if(node != null){
if(flag == true)
return false;
queue.add(node.left);
queue.add(node.right);
}else{
flag = true;
}
}
return true;
}
}
16. 樹的子結(jié)構(gòu)
劍指offer：樹的子結(jié)構(gòu)
輸入兩棵二叉樹A，B蛉签，判斷B是不是A的子結(jié)構(gòu)胡陪。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
return IsSubtree(root1, root2) ||
HasSubtree(root1.left, root2) ||
HasSubtree(root1.right, root2);
}
public boolean IsSubtree(TreeNode root1, TreeNode root2){
//要先判斷roo2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}這個(gè)測試用例通不過吻商。
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val == root2.val){
return IsSubtree(root1.left, root2.left) &&
IsSubtree(root1.right, root2.right);
}else
return false;
}
}
17. 二叉樹中和為某一值的路徑
劍指offer：二叉樹中和為某一值的路徑
輸入一顆二叉樹和一個(gè)整數(shù)往声，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑嗦玖。
public class Solution {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> temp = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if(root == null)
return res;
target -= root.val;
temp.add(root.val);
if(target == 0 && root.left == null && root.right == null)
res.add(new ArrayList<Integer>(temp));
else{
FindPath(root.left, target);
FindPath(root.right, target);
}
temp.remove(temp.size()-1);
return res;
}
}
18. 二叉樹的下一個(gè)結(jié)點(diǎn)
劍指offer：二叉樹的下一個(gè)結(jié)點(diǎn)
給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)片橡，請找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回妈经。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)捧书，同時(shí)包含指向父結(jié)點(diǎn)的指針吹泡。
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null){
return null;
}
if(pNode.right != null){
TreeLinkNode node = pNode.right;
while(node.left != null){
node = node.left;
}
return node;
}
while(pNode.next != null){
TreeLinkNode root = pNode.next;
if(pNode == root.left)
return root;
pNode = root;
}
return null;
}
}
19. 序列化二叉樹
劍指offer：序列化二叉樹
LeetCode：Serialize and Deserialize Binary Tree
請實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return "#,";
StringBuffer res = new StringBuffer(root.val + ",");
res.append(serialize(root.left));
res.append(serialize(root.right));
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String [] d = data.split(",");
Queue<String> queue = new LinkedList<>();
for(int i = 0; i < d.length; i++){
queue.offer(d[i]);
}
return pre(queue);
}
public TreeNode pre(Queue<String> queue){
String val = queue.poll();
if(val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}
20. 二叉搜索樹的第k個(gè)結(jié)點(diǎn)
劍指offer：二叉搜索樹的第k個(gè)結(jié)點(diǎn)
給定一棵二叉搜索樹经瓷，請找出其中的第k小的結(jié)點(diǎn)爆哑。例如， （5舆吮，3揭朝，7队贱，2，4潭袱，6露筒，8）中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4敌卓。
因?yàn)槎嫠阉鳂浒凑罩行虮闅v的順序打印出來就是排好序的慎式，所以，我們按照中序遍歷找到第k個(gè)結(jié)點(diǎn)就是題目所求的結(jié)點(diǎn)趟径。
class Solution {
public int kthSmallest(TreeNode root, int k) {
if(root == null)
return Integer.MIN_VALUE;
Stack<TreeNode> stack = new Stack<>();
int count = 0;
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
TreeNode node = stack.pop();
count ++;
if(count == k)
return node.val;
p = node.right;
}
}
return Integer.MIN_VALUE;
}
}
