二叉树

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;
    }
}