力扣——递增顺序查找树

不念不忘少年蓝@ 2021-11-10 03:08 211阅读 0赞

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。  
  
   
  
示例 ：  
  
输入：\[5,3,6,2,4,null,8,1,null,null,null,7,9\]  
  
       5  
      / \\  
    3    6  
   / \\    \\  
  2   4    8  
 /        / \\  
1        7   9  
  
输出：\[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9\]  
  
 1  
  \\  
   2  
    \\  
     3  
      \\  
       4  
        \\  
         5  
          \\  
           6  
            \\  
             7  
              \\  
               8  
                \\  
                 9    
  
   
  
提示：  
  
    给定树中的结点数介于 1 和 100 之间。  
    每个结点都有一个从 0 到 1000 范围内的唯一整数值。  
  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/increasing-order-search-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode increasingBST(TreeNode root) {
            LinkedList<Integer> list = new LinkedList<>();
            add(root,list);
            TreeNode res = new TreeNode(list.get(0));
            TreeNode node = res;
            for (int i = 1; i < list.size(); i++) {
                node.right = new TreeNode(list.get(i));
                node = node.right;
            }
            return res;
        }
        private void add(TreeNode node,LinkedList<Integer> list) {
            if (node == null) {
                return;
            }
            add(node.left,list);
            list.add(node.val);
            add(node.right,list);
        }
    }

转载于:https://www.cnblogs.com/JAYPARK/p/11256735.html