leetcode树专题894.897，919，951

满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。

返回包含 N 个结点的所有可能满二叉树的列表。答案的每个元素都是一个可能树的根结点。

答案中每个树的每个结点都必须有 node.val=0。

你可以按任何顺序返回树的最终列表。

示例：

输入：7

输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

解释：

提示：

1 <= N <= 20

递归做的，

贴代码：

public List<TreeNode> allPossibleFBT(int N) {

        List<TreeNode>list=new ArrayList<TreeNode>();

         TreeNode node=new TreeNode(0);

        if(N==0)

            return null;

        if(N==1){

            list.add(node);

            return list;

        }

        else{

            List<TreeNode>list1=new ArrayList<TreeNode>();

            for(int h=1;h<N-1;h++){

             if(h%2==0)

                continue;

             List<TreeNode>left=allPossibleFBT(h);

             List<TreeNode>right=allPossibleFBT(N-h-1);

            if(h==3){

                    //System.out.println(right.size());

                    //System.out.println(right.get(0).left.val);

                     //System.out.println(right.get(0).right.right.val);

                    //System.out.println(right.get(1).left.left.val);

                     //System.out.println(right.get(1).right.val);

               }

             for(int j=0;j<left.size();j++){

                for(int i=0;i<right.size();i++){

                      TreeNode node1=new TreeNode(0);

                     node1.left=left.get(j);

                    node1.right=right.get(i);

                    list1.add(node1);

                }

            }

        }

            return list1;

    }

    }

艾玛这题有点坑，刚开始我把TreeNode初始化放在第一层循环里面，结果解答错误，放在第二层循环就对了，求好心人告知这是什么原因，像下面这样。我是怎么发现这个的呢。我是实在找不到bug了，让一个大佬看看，然后他觉得放在里面好看于是挪进去，于是就通过了，我去，惊了。

897递增顺序查找树

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

示例：

输入：[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 范围内的唯一整数值。

树的题目做多了，发现遍历很重要，前序、中序、后序和层次遍历都应该掌握

  public TreeNode increasingBST(TreeNode root) {

        Stack <TreeNode>stack=new Stack<TreeNode>();

        List<Integer>re=new ArrayList<Integer>();

        int tag=0;

        while(root!=null||!stack.isEmpty()){

            while(root!=null){

                stack.push(root);

                root=root.left;

            }

            if(!stack.isEmpty()){

                TreeNode node=stack.pop();

               re.add(node.val);

                root=node.right;

            }

        }

        TreeNode next=new TreeNode(re.get(re.size()-1));

        for(int i=re.size()-2;i>=0;i--){

           TreeNode node=new TreeNode(re.get(i));

            node.right=next;

            next=node;

        }

        return next;

    }

919. 完全二叉树插入器

这题还是层次遍历的变形，当然我的这种做法并不好，用了243Ms,感觉快要超时了

class CBTInserter {

   TreeNode root;

    public CBTInserter(TreeNode root) {

       this.root=root;

    }

    public int insert(int v) {

       Queue <TreeNode>queue=new LinkedList<TreeNode>();

        queue.offer(root);

        int re=0;

        int flag=0;

        while(!queue.isEmpty()){

            for(int i=0;i<queue.size();i++){

                TreeNode node=queue.poll();

                if(node.left==null&&node.right==null){

                    node.left=new TreeNode(v);

                    re=node.val;

                    flag=1;

                }

                else if(node.right==null){

                    node.right=new TreeNode(v);

                    re=node.val;

                    flag=1;

                }

                else{

                    queue.offer(node.left);

                    queue.offer(node.right);

                }

               if(flag==1)

                    break;

            }

             if(flag==1)

                    break;

        }

        return re;

    }

    public TreeNode get_root() {

     return root;

    }

}

951.

翻转等价二叉树

简单的递归，嘿嘿

 public boolean flipEquiv(TreeNode root1, TreeNode root2) {

        if(root1==null&&root2==null)

            return true;

        else if(root1==null||root2==null)

            return false;

        if(root1.val!=root2.val)

            return false;

        if(root1.left==null&&root1.right==null&&root2.left==null&&root2.right==null)

            return true;

        boolean judge1=flipEquiv(root1.left,root2.left)&&flipEquiv(root2.right,root1.right);

        boolean judge2=flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left);

        return judge1||judge2;

    }

巴特西

leetcode树专题894.897，919，951

翻转等价二叉树

最新文章

热门文章