Sword finger offer II 052. flatten binary search tree (simple binary search tree DFS)

The finger of the sword Offer II 052. Flatten the binary search tree

Here's a binary search tree , please Traverse in middle order Rearrange it into an incremental sequential search tree , Make the leftmost node in the tree the root node of the tree , And each node has no left child , There is only one right child node .

Example 1：

Input ：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output ：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
Example 2：

Input ：root = [5,1,7]
Output ：[1,null,5,null,7]

Tips ：

The range of the number of nodes in the tree is [1, 100]
0 <= Node.val <= 1000

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/NYBBNL
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Because each node of the flattened binary tree has only the right child node , Create a new tree, directly traverse in order, and put the nodes on the right side of the tree in order .

Answer key （Java）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    private TreeNode ans = new TreeNode();
    private TreeNode temp = new TreeNode();

    public TreeNode increasingBST(TreeNode root) {
    
        temp = ans;
        dfs(root);
        return ans.right;
    }

    private void dfs(TreeNode root) {
    
        if (root == null) {
    
            return;
        }
        dfs(root.left);
        TreeNode node = new TreeNode(root.val);
        temp.right = node;
        temp = temp.right;
        dfs(root.right);
    }
}