根据先序遍历和中序遍历恢复二叉树

爱被打了一巴掌 2022-02-19 20:10 192阅读 0赞

> 这个思路上其实还是好理解的，就是每个树的先序遍历的第一个元素是这棵树的根节点，在中序遍历中这个根节点将树分割成左右子树（不一定全都存在）。先找到每个树（或者说是子树）的根节点在中序遍历的位置，递归的进行分割，返回根节点。但实现起来还是有很多地方有点讨厌的，特别是序列的位置表示。所以参考了别人的思路，将每棵子树分别用数组保存起来，这个就思路清晰了好多。

/** * 根据先序遍历和中序遍历恢复二叉树 */
    public class ReContructTree { 
        public static void main(String[] args) { 
            int pre[] = { 1, 2, 4, 7, 3, 5, 6, 8};
            int in[] = { 4, 7, 2, 1, 5, 3, 8, 6};
            TreeNode root = reConstructBinaryTree(pre, in);
            pre_order(root);
    
        }
    
        public static TreeNode reConstructBinaryTree(int[] pre, int[] in) { 
            if (pre == null || pre.length == 0 || in == null || in.length == 0)
                return null;
            else if (pre.length == 1 && in.length == 1) { 
                TreeNode root = new TreeNode(pre[0]);
                root.left = null;
                root.right = null;
                return root;
            } else { 
                TreeNode root = new TreeNode(pre[0]);
                int in_mid = -1;
                for (int i = 0; i < in.length; i++) { 
                    if (in[i] == pre[0]) { 
                        in_mid = i;//中序遍历的根节点
                        break;
                    }
                }
                //构造左子树
                if (in_mid > 0) { //in_mid中序遍历的根节点为0，无左子树
                    int pr[] = new int[in_mid];
                    int in_temp[] = new int[in_mid];
                    for (int i = 0; i < in_mid; i++) { 
                        pr[i] = pre[i + 1];
                        in_temp[i] = in[i];
                    }
                    root.left = reConstructBinaryTree(pr, in_temp);
                } else root.left = null;
                //构造右子树
                int len = pre.length;
                if (in_mid < pre.length - 1) { 
                    int pr[] = new int[len - 1 - in_mid];
                    int in_temp[] = new int[len - 1 - in_mid];
                    for (int i = in_mid + 1, j = 0; i < len; i++, j++) { 
                        pr[j] = pre[i];
                        in_temp[j] = in[i];
                    }
                    root.right = reConstructBinaryTree(pr, in_temp);
                } else root.right = null;
    
                return root;
            }
        }
    
    //
        public static void pre_order(TreeNode root) { 
            if (root != null) { 
                System.out.println(root.val);
                pre_order(root.left);
                pre_order(root.right);
            }
        }
    
    
    }
    
    // Definition for binary tree
    class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) { 
            val = x;
        }
    }