二叉树构建代码疑问：第二个版本构建的树为何解码结果错误？

嗨，我帮你仔细对比了两段构建二叉树的代码，找到了导致解码错误的两个关键问题——都是看起来细微但影响巨大的逻辑差异：

正确的树构建代码 #

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//set irrelevant node value to be '0'
    curr = root->left = getNode('0');
    curr->left = getNode('b');
    curr->right = getNode('g');
    curr = root->right = getNode('0');
    curr->right = getNode('e');
    curr = curr->left = getNode('0');
    curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->right = getNode('d');
    curr = curr->left = getNode('0');
    curr->left = getNode('c');
    curr->right = getNode('f');
    return root;

}

存在问题的树构建代码 #

Tree* buildTree() {
    Tree* root, * curr;
    root = getNode('0');//不是解码关键节点的点，值都设为‘0’,*100
    root->left =root->right = getNode('0');
    root->left->left = getNode('b');//19
    root->left->right = getNode('g');//21
    root->right->right = getNode('e');
    curr = root->right->left = getNode('0');
    curr->left = curr->right = getNode('0');
    curr->right->left = getNode('a');
    curr->right->right = getNode('h');
    curr = curr->left = getNode('0');
    curr->left = getNode('0');
    curr->right = getNode('d');
    curr->left->left = getNode('c');
    curr->left->right = getNode('f');
    return root;

}

问题分析 #

1. 致命错误：root的左右子节点指向了同一个实例
   错误版本里用了连等写法：root->left = root->right = getNode('0');
   这种写法会让root->left和root->right同时指向同一个Tree节点对象，而不是各自创建独立的节点。后续你对root->left的子节点（比如设置b和g）会直接影响root->right的结构，因为它们是同一个节点，这完全偏离了目标树的结构。

   正确的写法应该是分开赋值，确保左右子节点是独立的：

   root->left = getNode('0');
   root->right = getNode('0');
   

2. curr指针移动逻辑错误，导致节点层级错位
   错误版本里处理最内层节点时：

   curr = curr->left = getNode('0');
   curr->left = getNode('0');
   curr->right = getNode('d');
   curr->left->left = getNode('c');
   curr->left->right = getNode('f');
   

   这里你先给curr指向的节点的left赋值了新节点，然后直接操作这个新节点的左右子节点。但正确版本里的逻辑是：

   curr = curr->left = getNode('0');
   curr->right = getNode('d');
   curr = curr->left = getNode('0');
   curr->left = getNode('c');
   curr->right = getNode('f');
   

   正确逻辑是把curr指针移动到新创建的left节点后，再给这个节点的左右子节点赋值，这样curr始终指向当前要操作的层级，不会出现节点嵌套错误。

这两个问题叠加起来，就导致错误版本构建的树和你需要的目标树结构完全不符，解码自然会失败。修正这两个点后，代码就能正常工作了。

备注：内容来源于stack exchange，提问作者lylybay