构建二叉树

红太狼 2022-11-14 11:58 162阅读 0赞

### 构建二叉树 ###

*  根据前序遍历构建二叉树
 *   *  问题
     *  思路
 *  根据前序遍历+中序遍历
 *   *  题目：
 *  根据后序遍历+中序遍历
 *   *  题目：

# 根据前序遍历构建二叉树 #

如何构建二叉树呢，我们如果只单纯通过前序遍历，很难确定唯一的二叉树，因为会有很多种样式。

例如：前序序列为 A B C就可以构建很多的二叉树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]  
所以我们要想通过前序遍历构建唯一的二叉树，需要将空节点也带上，这样便可以构建唯一的二叉树。

## 问题 ##

牛客网链接：[二叉树构建和遍历][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

## 思路 ##

我们需要拿到一段二叉树的前序序列，首先可以得到头结点，’\#‘代表结点为空，当遇到’\#'的时候，便返回。知道将序列使用完成。  
如上题目：构建的二叉树样子应该为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
实现：

import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    /** * */
     //构建结点
    class TreeNode { 
        public char val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(char val) { 
            this.val = val;
        }
    }
    
    
    public class Main { 
    	//构建二叉树
        public static TreeNode buildTree(List<Character> preorder) { 
            if (preorder.isEmpty()) { 
                return null;
            }
            char rootval = preorder.remove(0);
            if (rootval == '#') { 
                return null;
            }
            TreeNode root = new TreeNode(rootval);
            root.left = buildTree(preorder);
            root.right = buildTree(preorder);
            return root;
        }
        //中序遍历
        public static void inorder(TreeNode root) { 
            if (root == null) { 
                return;
            }
            inorder(root.left);
            System.out.println(root.val);
            inorder(root.right);
        }
        
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextLine()) { 
                String s = scanner.nextLine();
                char[] p = s.toCharArray();
    
                List<Character> list = new ArrayList<>();
                for (char c : p) { 
                    list.add(c);
                }
    
                TreeNode root = buildTree(list);
    
                inorder(root);
    
                System.out.println();
            }
        }
    }

# 根据前序遍历+中序遍历 #

当我们已知前序和中序遍历的序列的时候，是否能构建唯一的二叉树呢？当然是可以的。  
已知前序序列，我们可以找到根节点，然后在中序序列中确定左子树和右子树个数。  
如此循环往复构建二叉树。

## 题目： ##

链接：  
[105. 从前序与中序遍历序列构造二叉树][105.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

class Solution { 
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            if (preorder.length == 0) { 
                return null;
            }
            int rootVal = preorder[0];
            TreeNode root = new TreeNode(rootVal);
    
            int size = 0;
            for (int i = 0; i < inorder.length; i++) { 
                if (inorder[i] == rootVal) { 
                    size = i;
                }
            }
            
            //构建左子树
            int[] leftpreorder = Arrays.copyOfRange(preorder, 1, size + 1);
            int[] leftinorder = Arrays.copyOfRange(inorder, 0, size);
            root.left = buildTree(leftpreorder, leftinorder);
    
            //构建右子树
            int[] rightpreorder = Arrays.copyOfRange(preorder, size + 1, preorder.length);
            int[] rightinorder = Arrays.copyOfRange(inorder, size + 1, inorder.length);
            root.right = buildTree(rightpreorder, rightinorder);
            return root;
        }
    }

# 根据后序遍历+中序遍历 #

和前序遍历与中序遍历求解二叉树类似，后序遍历我们也可以得到根节点…

## 题目： ##

[106. 从中序与后序遍历序列构造二叉树][106.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]

class Solution { 
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
            if (postorder.length == 0) { 
                return null;
            }
            int rootVal = postorder[postorder.length - 1];
            TreeNode root = new TreeNode(rootVal);
            int size = 0;
            for (int i = 0; i < inorder.length; i++) { 
                if (inorder[i] == rootVal) { 
                    size = i;
                }
            }
    
            int[] leftPostorder = Arrays.copyOfRange(postorder, 0, size);
            int[] leftInorder = Arrays.copyOfRange(inorder, 0, size);
            root.left = buildTree(leftInorder, leftPostorder);
            
            int[] rightPostorder = Arrays.copyOfRange(postorder,size,postorder.length-1);
            int[] rightInorder = Arrays.copyOfRange(inorder,size+1,inorder.length)  ;
            root.right = buildTree(rightInorder, rightPostorder);
            
            return root; 
        }
    }

我们那前序遍历和后序遍历构建不出唯一确定的二叉树，因为两种都只能确定根节点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/ea2c7428fb7443ff9df50da3132de60d.png
[Link 1]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/d6c8a1925edc4365abc9aaeceec03a6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/47bd110b73234c788f2385900ca35a57.png
[105.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/e8a5263e57d144cea8fc607302fac65b.png
[106.]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: /images/20221022/76de7be08602440788a0fb9a6b04af07.png