发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题意

给定一颗二叉搜索树，重新进行排序，使其根节点是最小值，且每个节点都没有左子树，只有一个右子树，最终还要保持该树是一颗二叉搜索树.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
例 1:
给予树:

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

输出:

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

解法

使用中序遍历即可。

阅读全文 »

发表于 | 分类于 | 评论数： | 阅读次数：

题意

给定一颗 N 叉树 的根节点，返回后序遍历后的数组.

例 :

1
2
3
4
5
6
7
给予树：
         1 
       / | \ 
      3  2  4
     / \ 
    5   6 
将其后序遍历返回: [5,6,3,2,4,1].

解法

和二叉树的中序遍历差不多，需要注意处理好子节点的顺序即可。

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题意

给定一颗 N 叉树 的根节点，返回树的深度.

例 :

1
2
3
4
5
6
7
给予树：
         1 
       / | \ 
      3  2  4
     / \ 
    5   6 
返回深度 3.

解法

采用 DFS (深度优先算法)，代码比较简单，不再赘言。

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题意

给定一颗 N 叉树 的根节点，返回前序遍历后的数组.

例 :

1
2
3
4
5
6
7
给予树：
         1 
       / | \ 
      3  2  4
     / \ 
    5   6 
将其前序遍历返回: [1,3,5,6,2,4].

解法

和二叉树的前序遍历差不多，需要注意处理好子节点的顺序即可。

阅读全文 »

发表于 | 分类于 | 评论数： | 阅读次数：

题意

判断二叉树是否是 唯一二叉树. 当树中所有节点的值都一样时，我们认为他是一颗 唯一二叉树。

1
2
3
4
5
6
7
给予一棵树:
        1
       / \
      1   1
     / \
    1   1
应当返回 `true`
1
2
3
4
5
6
7
给予一棵树:
        1
       / \
      1   1
     / \
    5   1
应当返回 `false`
阅读全文 »

发表于 | 分类于 | 评论数： | 阅读次数：

题意

给定一颗 二叉搜索树 的根节点，和一个要插入的值，将值插入进去，并返回根节点

  • 保证原树中不存在新值
  • 只要保证返回的树同样也是 二叉搜索树 即可

例:

1
2
3
4
5
6
给予一棵树:
        4
       / \
      2   7
     / \
    1   3

对于搜索值: 2, 你应该返回以下子树:

1
2
3
  2     
 / \   
1   3

阅读全文 »