LeetCode每日一题——897. 递增顺序搜索树（深度优先搜索 递归 树）

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public TreeNode increasingBST(TreeNode root) {
18         List<Integer> list = new ArrayList<>();
19         middleOrderTraversal(root, list);
20 
21         TreeNode newRoot = new TreeNode(list.get(0));
22 
23         dfs(newRoot, list, 1);
24 
25         return newRoot;
26     }
27 
28     public void dfs(TreeNode root, List<Integer> list, int cur) {
29         if (cur == list.size()) {
30             return;
31         }
32 
33         TreeNode newNode = new TreeNode(list.get(cur));
34         root.right = newNode;
35         dfs(newNode, list, cur + 1);
36     }
37 
38     // 中序遍历
39     public void middleOrderTraversal(TreeNode root, List<Integer> list) {
40         if (root == null) {
41             return;
42         }
43 
44         if (root.left != null) {
45             middleOrderTraversal(root.left, list);
46         }
47         list.add(root.val);
48         if (root.right != null) {
49             middleOrderTraversal(root.right, list);
50         }
51     }
52 }