LCP 67. 裝飾樹【深度周遊BFS】

力扣嘉年華上的 DIY 手工展位準備了一棵縮小版的 二叉 裝飾樹 

root

 和燈飾，你需要将燈飾逐一插入裝飾樹中，要求如下：

• 完成裝飾的二叉樹根結點與 

  root

   的根結點值相同
• 若一個節點擁有父節點，則在該節點和他的父節點之間插入一個燈飾（即插入一個值為 

  -1

   的節點）。具體地：
  • 在一個 父節點 x 與其左子節點 y 之間添加 -1 節點， 節點 -1、節點 y 為各自父節點的左子節點，
  • 在一個 父節點 x 與其右子節點 y 之間添加 -1 節點， 節點 -1、節點 y 為各自父節點的右子節點

現給定二叉樹的根節點 

root

 ，請傳回完成裝飾後的樹的根節點。 示例 1：

輸入： 

root = [7,5,6]

輸出：

[7,-1,-1,5,null,null,6]

解釋：如下圖所示

思路：

運用深度優先搜尋BFS，即層序周遊

原理是遞歸周遊

/**
 * 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 {
    public TreeNode expandBinaryTree(TreeNode root) {
        ArrayList<Integer> Nodelists=new ArrayList<>();//隊列存放節點
        return bfsTree(root);
    }

    public TreeNode bfsTree(TreeNode root){
        if(root==null){
            return null;
        }
        if(root.left!=null){
            TreeNode a=root.left;
            root.left=new TreeNode(-1);
            root.left.left=a;
            root.left.right=null;
            bfsTree(a);
        }
        if(root.right!=null){
            TreeNode a=root.right;
            root.right=new TreeNode(-1);
            root.right.right=a;
            root.right.left=null;
            bfsTree(a);
        }
        return root;
        
    }

}