二叉树
分类:
IT文章
•
2022-04-21 11:43:47
1、二叉树的遍历
(1)递归遍历
Java实现:
package com.demo.tree;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
orderTree.preOrderTree(root);
System.out.println();
orderTree.inOrederTree(root);
System.out.println();
orderTree.postOrderTree(root);
}
public void preOrderTree(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.data + " ");
preOrderTree(root.left);
preOrderTree(root.right);
}
public void inOrederTree(TreeNode root) {
if (root == null) {
return;
}
inOrederTree(root.left);
System.out.print(root.data + " ");
inOrederTree(root.right);
}
public void postOrderTree(TreeNode root) {
if (root == null) {
return;
}
postOrderTree(root.left);
postOrderTree(root.right);
System.out.print(root.data + " ");
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2
3 using namespace std;
4
5 class TreeNode
6 {
7 public:
8 int data;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(){}
12 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
13 };
14
15 //先序建立二叉树
16 TreeNode *createTree()
17 {
18 TreeNode *T;
19 int data;
20 cin >> data;
21 if (data == 0)
22 T = nullptr;
23 else
24 {
25 T = new TreeNode();
26 T->data = data;
27 T->left = createTree();
28 T->right = createTree();
29 }
30
31 return T;
32 }
33
34 //递归先序遍历二叉树
35 void preOrderTree(TreeNode* root)
36 {
37 if (root == nullptr)
38 return;
39 cout << root->data << " ";
40 preOrderTree(root->left);
41 preOrderTree(root->right);
42 }
43
44 //递归中序遍历二叉树
45 void inOrderTree(TreeNode* root)
46 {
47 if (root == nullptr)
48 return;
49 inOrderTree(root->left);
50 cout << root->data << " ";
51 inOrderTree(root->right);
52 }
53
54 //递归后序遍历二叉树
55 void postOrderTree(TreeNode *root)
56 {
57 if (root == nullptr)
58 return;
59 postOrderTree(root->left);
60 postOrderTree(root->right);
61 cout << root->data << " ";
62 }
63
64 int main()
65 {
66 //5 3 1 0 0 4 0 0 8 0 9 0 0
67 TreeNode *root = createTree();
68 preOrderTree(root);
69 cout << endl;
70 inOrderTree(root);
71 cout << endl;
72 postOrderTree(root);
73 cout << endl;
74
75 return 0;
76 }
View Code
(2)非递归遍历
Java实现:
package com.demo.tree;
import java.util.Scanner;
import java.util.Stack;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
orderTree.preOrderTree(root);
System.out.println();
orderTree.inOrederTree(root);
System.out.println();
orderTree.postOrderTree(root);
}
public void preOrderTree(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(root);
while (!stk.isEmpty()) {
root = stk.pop();
System.out.print(root.data + " ");
if (root.right != null) {
stk.push(root.right);
}
if (root.left != null) {
stk.push(root.left);
}
}
}
public void inOrederTree(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stk = new Stack<TreeNode>();
while (root != null || !stk.isEmpty()) {
if (root != null) {
stk.push(root);
root = root.left;
} else {
root = stk.pop();
System.out.print(root.data + " ");
root = root.right;
}
}
}
public void postOrderTree(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stk1 = new Stack<TreeNode>();
Stack<TreeNode> stk2 = new Stack<TreeNode>();
stk1.push(root);
while (!stk1.isEmpty()) {
root = stk1.pop();
stk2.push(root);
if (root.left != null) {
stk1.push(root.left);
}
if (root.right != null) {
stk1.push(root.right);
}
}
while (!stk2.isEmpty()) {
root = stk2.pop();
System.out.print(root.data + " ");
}
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2 #include<stack>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //先序遍历二叉树
36 void preOrderTree(TreeNode* root)
37 {
38 if (root == nullptr)
39 return;
40 stack<TreeNode*> stk;
41 stk.push(root);
42 while (!stk.empty())
43 {
44 root = stk.top();
45 stk.pop();
46 cout << root->data << " ";
47 if (root->right)
48 stk.push(root->right);
49 if (root->left)
50 stk.push(root->left);
51 }
52 }
53
54 //中序遍历二叉树
55 void inOrderTree(TreeNode* root)
56 {
57 if (root == nullptr)
58 return;
59 stack<TreeNode*> stk;
60 while (root || !stk.empty())
61 {
62 if (root)
63 {
64 stk.push(root);
65 root = root->left;
66 }
67 else
68 {
69 root = stk.top();
70 stk.pop();
71 cout << root->data << " ";
72 root = root->right;
73 }
74 }
75 }
76
77 //后序遍历二叉树
78 void postOrderTree(TreeNode *root)
79 {
80 if (root == nullptr)
81 return;
82 stack<TreeNode*> stk1;
83 stack<TreeNode*> stk2;
84 stk1.push(root);
85 while (!stk1.empty())
86 {
87 root = stk1.top();
88 stk1.pop();
89 stk2.push(root);
90 if (root->left)
91 stk1.push(root->left);
92 if (root->right)
93 stk1.push(root->right);
94 }
95 while (!stk2.empty())
96 {
97 root = stk2.top();
98 stk2.pop();
99 cout << root->data << " ";
100 }
101 }
102
103 int main()
104 {
105 //5 3 1 0 0 4 0 0 8 0 9 0 0
106 TreeNode *root = createTree();
107 preOrderTree(root);
108 cout << endl;
109 inOrderTree(root);
110 cout << endl;
111 postOrderTree(root);
112 cout << endl;
113
114 return 0;
115 }
View Code
(3)按层遍历
Java实现:
package com.demo.tree;
import java.util.LinkedList;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
orderTree.levelOrderTree(root);
}
public void levelOrderTree(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
int curNode = 1;
while (!que.isEmpty()) {
root = que.poll();
--curNode;
System.out.print(root.data + " ");
if (root.left != null) {
que.offer(root.left);
}
if (root.right != null) {
que.offer(root.right);
}
if (curNode == 0) {
System.out.println();
curNode = que.size();
}
}
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //按层遍历二叉树
36 void levelOrderTree(TreeNode* root)
37 {
38 if (root == nullptr)
39 return;
40 queue<TreeNode*> que;
41 que.push(root);
42 int i = 1;
43 while (!que.empty())
44 {
45 root = que.front();
46 que.pop();
47 --i;
48 cout << root->data << " ";
49 if (root->left)
50 que.push(root->left);
51 if (root->right)
52 que.push(root->right);
53 if (i == 0)
54 {
55 cout << endl;
56 i = que.size();
57 }
58 }
59 }
60
61
62 int main()
63 {
64 //5 3 1 0 0 4 0 0 8 0 9 0 0
65 TreeNode *root = createTree();
66 levelOrderTree(root);
67
68 return 0;
69 }
View Code
2、求二叉树的结点数
Java实现:
package com.demo.tree;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
int nodes = orderTree.getCountNodes(root);
System.out.println(depth);
}
public int getCountNodes(TreeNode root) {
if (root == null) {
return 0;
}
return getCountNodes(root.left) + getCountNodes(root.right) + 1;
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //求树的结点数
36 int CountNodes(TreeNode* root)
37 {
38 if (root == nullptr)
39 return 0;
40 return CountNodes(root->left) + CountNodes(root->right) + 1;
41 }
42
43
44 int main()
45 {
46 //5 3 1 0 0 4 0 0 8 0 9 0 0
47 TreeNode *root = createTree();
48 int nodes=CountNodes(root);
49 cout << nodes << endl;
50
51 return 0;
52 }
View Code
3、求二叉树的叶子结点数
Java实现:
package com.demo.tree;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
int nodes = orderTree.getLevelCountNodes(root);
System.out.println(depth);
}
public int getLevelCountNodes(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLevelCountNodes(root.left) + getLevelCountNodes(root.right);
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //求树的叶子结点数
36 int countLevelNodes(TreeNode* root)
37 {
38 if (root == nullptr)
39 return 0;
40 if (!root->left && !root->right)
41 return 1;
42 return countLevelNodes(root->left) + countLevelNodes(root->right);
43 }
44
45
46 int main()
47 {
48 //5 3 1 0 0 4 0 0 8 0 9 0 0
49 TreeNode *root = createTree();
50 int nodes=countLevelNodes(root);
51 cout << nodes << endl;
52
53 return 0;
54 }
View Code
4、求树的深度
Java实现:
(1)递归
package com.demo.tree;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
int depth = orderTree.getDepth(root);
System.out.println(depth);
}
public int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getDepth(root.left);
int right = getDepth(root.right);
return left > right ? (left + 1) : (right + 1);
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
(2)非递归
package com.demo.tree;
import java.util.LinkedList;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
int depth = orderTree.getDepth(root);
System.out.println(depth);
}
public int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
int level = 0;
int curNode = 1;
while (!que.isEmpty()) {
root = que.poll();
--curNode;
if (root.left != null) {
que.offer(root.left);
}
if (root.right != null) {
que.offer(root.right);
}
if (curNode == 0) {
++level;
curNode = que.size();
}
}
return level;
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
(1)递归
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //求树的深度
36 int getDepth(TreeNode* root)
37 {
38 if (root == nullptr)
39 return 0;
40 int left=getDepth(root->left);
41 int right=getDepth(root->right);
42 return left>right?(left+ 1):(right+1);
43 }
44
45
46 int main()
47 {
48 //5 3 1 0 0 4 0 0 8 0 9 0 0
49 TreeNode *root = createTree();
50 int depth=getDepth(root);
51 cout << depth << endl;
52
53 return 0;
54 }
View Code
(2)非递归
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 //求树的深度
36 int getDepth(TreeNode* root)
37 {
38 if (root == nullptr)
39 return 0;
40 queue<TreeNode*> que;
41 que.push(root);
42 int level = 0;
43 int i = 1;
44 while (!que.empty())
45 {
46 root = que.front();
47 que.pop();
48 --i;
49 if (root->left)
50 que.push(root->left);
51 if (root->right)
52 que.push(root->right);
53 if (i == 0)
54 {
55 i = que.size();
56 ++level;
57 }
58 }
59 return level;
60 }
61
62
63 int main()
64 {
65 //5 3 1 0 0 4 0 0 8 0 9 0 0
66 TreeNode *root = createTree();
67 int depth=getDepth(root);
68 cout << depth << endl;
69
70 return 0;
71 }
View Code
5、求二叉树第 k 层的结点个数
Java实现:
package com.demo.tree;
import java.util.Scanner;
public class OrderTree {
public static void main(String[] args) {
OrderTree orderTree = new OrderTree();
//5 3 1 0 0 4 0 0 8 0 9 0 0
TreeNode root = orderTree.createTree();
int nodes = orderTree.getKLevel(root, 2);
System.out.println(nodes);
}
public int getKLevel(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevel(root.left, k - 1) + getKLevel(root.right, k - 1);
}
public TreeNode createTree() {
TreeNode tree;
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
if (data == 0) {
tree = null;
} else {
tree = new TreeNode();
tree.data = data;
tree.left = createTree();
tree.right = createTree();
}
return tree;
}
}
class TreeNode {
public int data;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
C++实现:
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 int getKLevel(TreeNode* root,int k)
36 {
37 if (root == nullptr)
38 return 0;
39
40 if (k == 1)
41 return 1;
42 return getKLevel(root->left, k - 1) + getKLevel(root->right, k - 1);
43 }
44
45
46 int main()
47 {
48 //5 3 1 0 0 4 0 0 8 0 9 0 0
49 TreeNode *root = createTree();
50 int nodes=getKLevel(root,2);
51 cout << nodes << endl;
52
53 return 0;
54 }
View Code
6、判断两棵二叉树是否结构相同
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 bool sameTree(TreeNode* node1, TreeNode* node2)
36 {
37 if (!node1 && !node2)
38 return true;
39 else if (!node1 || !node2)
40 return false;
41 else
42 {
43 if (node1->data != node2->data)
44 return false;
45 else
46 return sameTree(node1->left, node2->left) && sameTree(node1->right, node2->right);
47 }
48 }
49
50
51 int main()
52 {
53 //5 3 1 0 0 4 0 0 8 0 9 0 0
54 TreeNode *node1 = createTree();
55 TreeNode *node2 = createTree();
56 cout << sameTree(node1, node2) << endl;
57
58 return 0;
59 }
View Code
7、求二叉树的镜像
对于每个结点交换它的左右孩子即可。
(1)递归
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 void mirror(TreeNode *root)
36 {
37 if (root == nullptr)
38 return;
39 TreeNode* tmp = root->left;
40 root->left = root->right;
41 root->right = tmp;
42 mirror(root->left);
43 mirror(root->right);
44 }
45
46 void levelOrderTree(TreeNode* root)
47 {
48 if (root == nullptr)
49 return;
50 queue<TreeNode*> que;
51 que.push(root);
52 int i = 1;
53 while (!que.empty())
54 {
55 root = que.front();
56 que.pop();
57 --i;
58 cout << root->data << " ";
59 if (root->left)
60 que.push(root->left);
61 if (root->right)
62 que.push(root->right);
63 if (i == 0)
64 {
65 cout << endl;
66 i = que.size();
67 }
68 }
69 }
70
71 int main()
72 {
73 //5 3 1 0 0 4 0 0 8 0 9 0 0
74 TreeNode *node = createTree();
75 levelOrderTree(node);
76 mirror(node);
77 levelOrderTree(node);
78
79 return 0;
80 }
View Code
(2)递归
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode() {}
13 TreeNode(int val) :data(val), left(nullptr), right(nullptr) {}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 TreeNode* mirror(TreeNode *root)
36 {
37 if (root == nullptr)
38 return root;
39 TreeNode* left = mirror(root->left);
40 TreeNode* right = mirror(root->right);
41 root->left = right;
42 root->right = left;
43
44 return root;
45 }
46
47 void levelOrderTree(TreeNode* root)
48 {
49 if (root == nullptr)
50 return;
51 queue<TreeNode*> que;
52 que.push(root);
53 int i = 1;
54 while (!que.empty())
55 {
56 root = que.front();
57 que.pop();
58 --i;
59 cout << root->data << " ";
60 if (root->left)
61 que.push(root->left);
62 if (root->right)
63 que.push(root->right);
64 if (i == 0)
65 {
66 cout << endl;
67 i = que.size();
68 }
69 }
70 }
71
72 int main()
73 {
74
75 TreeNode *node = createTree();
76 levelOrderTree(node);
77 TreeNode *res = mirror(node);
78 levelOrderTree(res);
79
80 return 0;
81 }
View Code
(3)非递归
1 #include<iostream>
2 #include<queue>
3 #include<stack>
4
5 using namespace std;
6
7 class TreeNode
8 {
9 public:
10 int data;
11 TreeNode *left;
12 TreeNode *right;
13 TreeNode(){}
14 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
15 };
16
17 //先序建立二叉树
18 TreeNode *createTree()
19 {
20 TreeNode *T;
21 int data;
22 cin >> data;
23 if (data == 0)
24 T = nullptr;
25 else
26 {
27 T = new TreeNode();
28 T->data = data;
29 T->left = createTree();
30 T->right = createTree();
31 }
32
33 return T;
34 }
35
36 void mirror(TreeNode *root)
37 {
38 if (root == nullptr)
39 return;
40 stack<TreeNode*> stk;
41 stk.push(root);
42 while (!stk.empty())
43 {
44 root = stk.top();
45 stk.pop();
46 TreeNode *tmp = root->left;
47 root->left = root->right;
48 root->right = tmp;
49 if (root->right)
50 stk.push(root->right);
51 if (root->left)
52 stk.push(root->left);
53 }
54 }
55
56 void levelOrderTree(TreeNode* root)
57 {
58 if (root == nullptr)
59 return;
60 queue<TreeNode*> que;
61 que.push(root);
62 int i = 1;
63 while (!que.empty())
64 {
65 root = que.front();
66 que.pop();
67 --i;
68 cout << root->data << " ";
69 if (root->left)
70 que.push(root->left);
71 if (root->right)
72 que.push(root->right);
73 if (i == 0)
74 {
75 cout << endl;
76 i = que.size();
77 }
78 }
79 }
80
81 int main()
82 {
83 //5 3 1 0 0 4 0 0 8 0 9 0 0
84 TreeNode *node = createTree();
85 levelOrderTree(node);
86 mirror(node);
87 levelOrderTree(node);
88
89 return 0;
90 }
View Code
8、判断一颗二叉树是否是镜像二叉树
1 #include<iostream>
2 #include<queue>
3 #include<stack>
4
5 using namespace std;
6
7 class TreeNode
8 {
9 public:
10 int data;
11 TreeNode *left;
12 TreeNode *right;
13 TreeNode(){}
14 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
15 };
16
17 //先序建立二叉树
18 TreeNode *createTree()
19 {
20 TreeNode *T;
21 int data;
22 cin >> data;
23 if (data == 0)
24 T = nullptr;
25 else
26 {
27 T = new TreeNode();
28 T->data = data;
29 T->left = createTree();
30 T->right = createTree();
31 }
32
33 return T;
34 }
35
36 bool helper(TreeNode* left, TreeNode* right)
37 {
38 if (!left && !right)
39 return true;
40 else if (!left || !right)
41 return false;
42 else if (left->data != right->data)
43 return false;
44 else
45 return helper(left->left, right->right) && helper(left->right, right->left);
46 }
47
48 bool isMirror(TreeNode *root)
49 {
50 if (root == nullptr)
51 return true;
52 return helper(root->left, root->right);
53 }
54
55 void levelOrderTree(TreeNode* root)
56 {
57 if (root == nullptr)
58 return;
59 queue<TreeNode*> que;
60 que.push(root);
61 int i = 1;
62 while (!que.empty())
63 {
64 root = que.front();
65 que.pop();
66 --i;
67 cout << root->data << " ";
68 if (root->left)
69 que.push(root->left);
70 if (root->right)
71 que.push(root->right);
72 if (i == 0)
73 {
74 cout << endl;
75 i = que.size();
76 }
77 }
78 }
79
80 int main()
81 {
82 TreeNode *node = createTree();
83 levelOrderTree(node);
84 cout << isMirror(node) << endl;
85
86 return 0;
87 }
View Code
9、求两个结点的最低公共祖先结点
1 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
2 {
3 if(root==nullptr||p==nullptr||q==nullptr)
4 return nullptr;
5 if(root==p||root==q)
6 return root;
7 TreeNode* left=lowestCommonAncestor(root->left,p,q);
8 TreeNode* right=lowestCommonAncestor(root->right,p,q);
9 if(left&&right)
10 return root;
11 return left?left:right;
12 }
View Code
10、求任意两结点距离
首先找到两个结点的 LCA,然后分别计算 LCA 与它们的距离,最后相加即可。
1 #include<iostream>
2
3 using namespace std;
4
5 class TreeNode
6 {
7 public:
8 int data;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(){}
12 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
13 };
14
15 TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
16 if (root == nullptr || p == nullptr || q == nullptr)
17 return nullptr;
18 if (root == p || root == q)
19 return root;
20 TreeNode* left = findLCA(root->left, p, q);
21 TreeNode* right = findLCA(root->right, p, q);
22 if (left&&right)
23 return root;
24 return left ? left : right;
25 }
26
27 int findLevel(TreeNode* lca, TreeNode* node)
28 {
29 if (lca == nullptr)
30 return -1;
31 if (lca == node)
32 return 0;
33 int level = findLevel(lca->left, node);// 先在左子树找
34 if (level == -1)
35 level = findLevel(lca->right, node);// 如果左子树没找到,在右子树找
36 if (level != -1)// 找到了,回溯
37 return level + 1;
38 return -1;
39 }
40
41 int distanceNodes(TreeNode* root, TreeNode* node1, TreeNode* node2)
42 {
43 TreeNode* lca = findLCA(root, node1, node2);
44 int level1 = findLevel(lca, node1);
45 int level2 = findLevel(lca, node2);
46 return level1 + level2;
47 }
View Code
11、找出二叉树中某个结点的所有祖先结点
1 #include<iostream>
2
3 using namespace std;
4
5 class TreeNode
6 {
7 public:
8 int data;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(){}
12 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
13 };
14
15 bool findAllAncestors(TreeNode* node, TreeNode * target)
16 {
17 if (node == nullptr)
18 return false;
19 if (node == target)
20 return true;
21 if (findAllAncestors(node->left, target) || findAllAncestors(node->right, target))
22 {
23 cout << node->data << " ";
24 return true;
25 }
26 return false;
27 }
View Code
12、已知二叉树前序中序,重建出该二叉树。
1 #include<iostream>
2 #include<vector>
3 #include<stack>
4
5 using namespace std;
6
7 class TreeNode
8 {
9 public:
10 int data;
11 TreeNode *left;
12 TreeNode *right;
13 TreeNode(){}
14 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
15 };
16
17
18 TreeNode* reConstructBinaryTree(vector<int> &pre, vector<int> &vin)
19 {
20 int size = vin.size();
21 if (size == 0)
22 return nullptr;
23 vector<int> pre_left, pre_right, in_left, in_right;
24 int val = pre[0];
25 TreeNode* root = new TreeNode(val);
26 int p = 0;
27 for (; p < size; ++p)
28 if (vin[p] == val)
29 break;
30 for (int i = 0; i < size; ++i)
31 {
32 if (i < p)
33 {
34 pre_left.push_back(pre[i + 1]);
35 in_left.push_back(vin[i]);
36 }
37 else if(i>p)
38 {
39 pre_right.push_back(pre[i]);
40 in_right.push_back(vin[i]);
41 }
42 }
43 root->left = reConstructBinaryTree(pre_left, in_left);
44 root->right = reConstructBinaryTree(pre_right, in_right);
45
46 return root;
47 }
48
49 void inOrderTree(TreeNode* root)
50 {
51 if (root == nullptr)
52 return;
53 stack<TreeNode*> stk;
54 while (root || !stk.empty())
55 {
56 if (root)
57 {
58 stk.push(root);
59 root = root->left;
60 }
61 else
62 {
63 root = stk.top();
64 stk.pop();
65 cout << root->data << " ";
66 root = root->right;
67 }
68 }
69 }
70
71 int main()
72 {
73 vector<int> pre = { 1,2,4,7,3,5,6,8 };
74 vector<int> vin = { 4,7,2,1,5,3,8,6 };
75 TreeNode* root = reConstructBinaryTree(pre, vin);
76 inOrderTree(root);
77
78 return 0;
79 }
View Code
13、判断二叉树是不是完全二叉树
若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树(Complete Binary Tree)。
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 bool isCompleteBinaryTree(TreeNode* root)
17 {
18 if (root == nullptr)
19 return false;
20 queue<TreeNode*> que;
21 que.push(root);
22 bool flag = false;
23 while (!que.empty())
24 {
25 TreeNode* node = que.front();
26 que.pop();
27 //已经出现了有空子树的节点了,后面出现的必须为叶节点(左右子树都为空)
28 if (flag)
29 {
30 if (node->left || node->right)
31 return false;
32 }
33 else
34 {
35 if (node->left&&node->right)
36 {
37 que.push(node->left);
38 que.push(node->right);
39 }
40 else if (node->left && !node->right)
41 {
42 que.push(node->left);
43 flag = true;
44 }
45 else if (!node->left&&node->right)
46 return false;
47 else
48 flag = true;
49 }
50 }
51 return true;
52 }
View Code
14、判断二叉树是不是平衡二叉树
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 bool isBalance = true;
17 bool IsBalanced_Solution(TreeNode* root) {
18 if (root == nullptr)
19 return true;
20 getDepth(root);
21 return isBalance;
22 }
23 int getDepth(TreeNode* root)
24 {
25 if (root == nullptr)
26 return 0;
27 int left = getDepth(root->left);
28 int right = getDepth(root->right);
29 if (abs(left - right)>1)
30 isBalance = false;
31 return max(left, right) + 1;
32 }
View Code
15、判断数组是不是某二叉搜索树的后序遍历的结果
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 bool verifySquenceOfBST(vector<int> arr) {
17 int size = arr.size();
18 if (size == 0)
19 return false;
20 if (size == 1)
21 return true;
22 return helper(arr, 0, size - 1);
23 }
24 bool helper(vector<int> arr, int start, int end)
25 {
26 if (start >= end)
27 return true;
28 int i = end;
29 while (i>start&&arr[i - 1]>arr[end])
30 --i;
31 for (int j = start; j<i; ++j)
32 if (arr[j]>arr[end])
33 return false;
34 return helper(arr, start, i - 1) && helper(arr, i, end - 1);
35 }
View Code
16、给定一个二叉查找树中的结点,找出在中序遍历下它的后继结点
一棵二叉查找树的中序遍历序列,正好是升序序列。
如果结点中有指向父亲结点的指针(假如根结点的父结点为 nullptr),则:
(1):如果当前结点有右孩子,则后继结点为这个右孩子的最左孩子;
(2):如果当前结点没有右孩子;
(2.1):当前结点为根结点,返回 nullptr;
(2.2):当前结点只是个普通结点,也就是存在父结点;
(2.2.1):当前结点是父亲结点的左孩子,则父亲结点就是后继结点;
(2.2.2):当前结点是父亲结点的右孩子,沿着父亲结点往上走,直到 n-1 代祖先是 n 代祖先的左孩子,则后继为 n 代祖
先或遍历到根结点也没找到符合的,则当前结点就是中序遍历的最后一个结点,返回 nullptr。
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode *parent;
13 TreeNode(){}
14 TreeNode(int val):data(val),left(nullptr),right(nullptr),parent(nullptr){}
15 };
16
17 TreeNode * Increment(TreeNode * node)
18 {
19 if (node->right) //(1)
20 {
21 node = node->right;
22 while (node->left)
23 node = node->left;
24 return node;
25 }
26 else //(2)
27 {
28 if (node->parent == nullptr) //(2.1)
29 return nullptr;
30 TreeNode * p = node->parent; //(2.2)
31 if (p->left == node) //(2.2.1)
32 return p;
33 else //(2.2.2)
34 {
35 while (p->right == node)
36 {
37 node = p;
38 p = p->parent;
39 if (p == nullptr)
40 return nullptr;
41 }
42 return p;
43 }
44 }
45 }
View Code
17、将二叉搜索树转换成一个排序的双向链表
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 TreeNode* Convert(TreeNode* root)
17 {
18 if (root == nullptr)
19 return root;
20 TreeNode* left = Convert(root->left);
21 TreeNode* right = Convert(root->right);
22 TreeNode* node = left;
23 while (node&&node->right)
24 node = node->right;
25 if (node)
26 {
27 node->right = root;
28 root->left = node;
29 }
30 if (right)
31 {
32 root->right = right;
33 right->left = root;
34 }
35 return left ? left : root;
36 }
View Code
18、有序链表转化为平衡的二分查找树
(1)采用自顶向下的方法。先找到中间结点作为根结点,然后递归左右两部分。需要先找到中间结点,对于单链表来说,必须要遍历一边,可以使用快慢指针加快查找速度。
由 f(n)=2f(n2)+n2 得,此算法的时间复杂度为 O(nlogn)。
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 class ListNode
17 {
18 public:
19 int val;
20 ListNode *next;
21 ListNode(){}
22 ListNode(int x):val(x),next(nullptr){}
23 };
24
25 ListNode* createList()
26 {
27 int in;
28 ListNode* head = nullptr;
29 cout << "enter list value (enter 100 to quit):";
30 cin >> in;
31 if (in == 100)
32 return head;
33 else
34 {
35 head = new ListNode(in);
36 head->next = createList();
37 }
38 return head;
39 }
40
41 TreeNode *sortedListToBST(ListNode* list)
42 {
43 if (!list)
44 return nullptr;
45 if (list && !list->next)
46 return new TreeNode(list->val);
47
48 ListNode* pre = nullptr;
49 ListNode* slow = list;
50 ListNode* fast = list;
51 while (fast&&fast->next)
52 {
53 pre = slow;
54 slow = slow->next;
55 fast = fast->next->next;
56 }
57 TreeNode* mid = new TreeNode(slow->val);
58 if (pre)
59 {
60 pre->next = nullptr;
61 mid->left = sortedListToBST(list);
62 }
63 mid->right = sortedListToBST(slow->next);
64 return mid;
65 }
66
67 void inOrderTree(TreeNode* root)
68 {
69 if (root == nullptr)
70 return;
71 inOrderTree(root->left);
72 cout << root->data << " ";
73 inOrderTree(root->right);
74 }
75 void preOrderTree(TreeNode* root)
76 {
77 if (root == nullptr)
78 return;
79 cout << root->data << " ";
80 preOrderTree(root->left);
81 preOrderTree(root->right);
82 }
83
84 int main()
85 {
86 ListNode* list = createList();
87 TreeNode* tree = sortedListToBST(list);
88 inOrderTree(tree);
89 cout << endl;
90 preOrderTree(tree);
91
92 return 0;
93 }
View Code
(2)采用自底向上的方法。 时间复杂度降为 O(n)。
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode(){}
13 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
14 };
15
16 class ListNode
17 {
18 public:
19 int val;
20 ListNode *next;
21 ListNode(){}
22 ListNode(int x):val(x),next(nullptr){}
23 };
24
25 ListNode* createList()
26 {
27 int in;
28 ListNode* head = nullptr;
29 cout << "enter list value (enter 100 to quit):";
30 cin >> in;
31 if (in == 100)
32 return head;
33 else
34 {
35 head = new ListNode(in);
36 head->next = createList();
37 }
38 return head;
39 }
40
41 TreeNode* helper(ListNode *&list, int start, int end)
42 {
43 if (start > end)
44 return nullptr;
45 int mid = start + (end - start) / 2;
46 TreeNode* left = helper(list, start, mid - 1);
47 TreeNode* parent = new TreeNode(list->val);
48 parent->left = left;
49 list = list->next;
50 parent->right = helper(list, mid + 1, end);
51 return parent;
52 }
53
54 TreeNode *sortedListToBST(ListNode* list)
55 {
56 if (!list)
57 return nullptr;
58 int n = 0;
59 ListNode* p = list;
60 while (p)
61 {
62 ++n;
63 p = p->next;
64 }
65 return helper(list, 0, n - 1);
66 }
67
68 void inOrderTree(TreeNode* root)
69 {
70 if (root == nullptr)
71 return;
72 inOrderTree(root->left);
73 cout << root->data << " ";
74 inOrderTree(root->right);
75 }
76 void preOrderTree(TreeNode* root)
77 {
78 if (root == nullptr)
79 return;
80 cout << root->data << " ";
81 preOrderTree(root->left);
82 preOrderTree(root->right);
83 }
84
85 int main()
86 {
87 ListNode* list = createList();
88 TreeNode* tree = sortedListToBST(list);
89 inOrderTree(tree);
90 cout << endl;
91 preOrderTree(tree);
92
93 return 0;
94 }
View Code
19、判断是否是二叉查找树。假定二叉树没有重复元素,即对于每个结点,其左右孩子都是严格的小于和大于。
1 #include<iostream>
2
3 using namespace std;
4
5 class TreeNode
6 {
7 public:
8 int data;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(){}
12 TreeNode(int val):data(val),left(nullptr),right(nullptr){}
13 };
14
15 TreeNode *createTree()
16 {
17 TreeNode *root;
18 int data;
19 cin >> data;
20 if (data == 0)
21 root = nullptr;
22 else
23 {
24 root = new TreeNode();
25 root->data = data;
26 root->left = createTree();
27 root->right = createTree();
28 }
29 return root;
30 }
31
32 bool isBST(TreeNode* node, int min, int max)
33 {
34 if (node == nullptr)
35 return true;
36 if (node->data <= min || node->data >= max)
37 return false;
38 return isBST(node->left, min, node->data) && isBST(node->right, node->data, max);
39 }
40
41 int main()
42 {
43 TreeNode* root = createTree();
44 cout << isBST(root, INT_MIN, INT_MAX) << endl;
45
46 return 0;
47 }
View Code
20、求二叉树中节点的最大距离,即二叉树中相距最远的两个节点之间的距离。
递归解法:
(1)如果二叉树为空,返回0,同时记录左子树和右子树的深度,都为0
(2)如果二叉树不为空,最大距离要么是左子树中的最大距离,要么是右子树中的最大距离,要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离,同时记录左子树和右子树节点中到根节点的最大距离。
1 #include<iostream>
2 #include<queue>
3
4 using namespace std;
5
6 class TreeNode
7 {
8 public:
9 int data;
10 TreeNode *left;
11 TreeNode *right;
12 TreeNode() {}
13 TreeNode(int val) :data(val), left(nullptr), right(nullptr) {}
14 };
15
16 //先序建立二叉树
17 TreeNode *createTree()
18 {
19 TreeNode *T;
20 int data;
21 cin >> data;
22 if (data == 0)
23 T = nullptr;
24 else
25 {
26 T = new TreeNode();
27 T->data = data;
28 T->left = createTree();
29 T->right = createTree();
30 }
31
32 return T;
33 }
34
35 int getMaxDistance(TreeNode * root, int & maxLeft, int & maxRight)
36 {
37 // maxLeft, 左子树中的节点距离根节点的最远距离
38 // maxRight, 右子树中的节点距离根节点的最远距离
39 if (root == nullptr)
40 {
41 maxLeft = 0;
42 maxRight = 0;
43 return 0;
44 }
45 int maxLL, maxLR, maxRL, maxRR;
46 int maxDistLeft, maxDistRight;
47 if (root->left)
48 {
49 maxDistLeft = getMaxDistance(root->left, maxLL, maxLR);
50 maxLeft = max(maxLL, maxLR) + 1;
51 }
52 else
53 {
54 maxDistLeft = 0;
55 maxLeft = 0;
56 }
57 if (root->right)
58 {
59 maxDistRight = getMaxDistance(root->right, maxRL, maxRR);
60 maxRight = max(maxRL, maxRR) + 1;
61 }
62 else
63 {
64 maxDistRight = 0;
65 maxRight = 0;
66 }
67 return max(max(maxDistLeft, maxDistRight), maxLeft + maxRight);
68 }
69
70 int main()
71 {
72
73 TreeNode *node = createTree();
74 int left = 0, right = 0;
75 cout << getMaxDistance(node,left,right) << endl;
76
77 return 0;
78 }
View Code
21、二叉树中和为某一值的路径
#include<iostream>
#include<vector>
using namespace std;
class TreeNode
{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode() {}
TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}
};
//先序建立二叉树
TreeNode *createTree()
{
TreeNode *T;
int data;
cin >> data;
if (data == 0)
T = nullptr;
else
{
T = new TreeNode();
T->val = data;
T->left = createTree();
T->right = createTree();
}
return T;
}
void helper(TreeNode* root, int num, vector<int> &path, vector<vector<int>> &res)
{
if (root == nullptr)
return;
path.push_back(root->val);
if (root->val == num&&root->left == nullptr&&root->right == nullptr)
{
res.push_back(path);
path.pop_back();
}
else
{
helper(root->left, num - root->val, path, res);
helper(root->right, num - root->val, path, res);
path.pop_back();
}
}
vector<vector<int> > findPath(TreeNode* root, int num) {
vector<vector<int>> res;
vector<int> path;
if (root == nullptr)
return res;
helper(root, num, path, res);
return res;
}
int main()
{
TreeNode *node = createTree();
int val = 9;
vector<vector<int>> res = findPath(node, val);
for (int i = 0; i < res.size(); ++i)
{
for (int j = 0; j < res[i].size(); ++j)
cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
22、二叉排序树中插入新的节点
package com.test.tree;
public class Main {
//测试
public static void main(String[] args) {
int a[] = {0, 5, 8, 4, 2, 3, 8, 10};
TreeNode root = null;
for (int i = 0; i < a.length; ++i) {
root = insertTreeNode(root, a[i]);
}
inorderTree(root);
}
//往二叉排序树中插入一个新节点(递归实现)
public static TreeNode insertTreeNodeRecursion(TreeNode root, int data) {
if (root == null) {
return new TreeNode(data);
} else {
TreeNode cur = null;
if (data <= root.data) {
cur = insertTreeNodeRecursion(root.left, data);
root.left = cur;
} else {
cur = insertTreeNodeRecursion(root.right, data);
root.right = cur;
}
}
return root;
}
//往二叉排序树中插入一个新节点(非递归实现)
public static TreeNode insertTreeNode(TreeNode root, int data) {
TreeNode node = new TreeNode(data);
if (root == null) {
return node;
} else {
TreeNode curNode = root;
while (true) {
if (data < curNode.data) {
if (curNode.left == null) {
curNode.left = node;
return root;
} else {
curNode = curNode.left;
}
} else if (data > curNode.data) {
if (curNode.right == null) {
curNode.right = node;
return root;
} else {
curNode = curNode.right;
}
} else {
System.out.println("已存在");
return root;
}
}
}
}
//中序遍历二叉树
public static void inorderTree(TreeNode root) {
if (root == null) {
return;
}
inorderTree(root.left);
System.out.print(root.data + " ");
inorderTree(root.right);
}
}
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
TreeNode() {
}
TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}