Инвертировать исходный код дерева

#java #binary-tree

#java #двоичное дерево

Вопрос:

Итак, я работаю над проблемой в LeetCode, где я должен инвертировать двоичное дерево.

Проблема:

и вот мое решение:

 class Solution {
    public TreeNode invertTree(TreeNode root) {
        TreeNode newTree = root;
        return invertTreeHelper(root, newTree);
    }

    public TreeNode invertTreeHelper(TreeNode root, TreeNode newTree)
    {
       if(root == null)
           return null; 
        
       newTree.val = root.val;         
       newTree.left = invertTreeHelper(root.right, newTree.left); 
       newTree.right = invertTreeHelper(root.left, newTree.right); 
       return newTree; 
    }
}

Заданный ввод:

 [4,2,7,1,3,6,9]

Мой ожидаемый результат:

 [4,7,2,9,6,3,1]

Тем не менее, мой вывод:

 [4,7,7,9,6,6,9]

Итак, очевидно, что мой вывод не работает для левой части дерева. Я хочу знать, где я ошибся. Может ли кто-нибудь, пожалуйста, помочь мне с этим?

1. Проблема, с которой вы сталкиваетесь, заключается в том, что вы заменяете left на right, а затем заменяете right новым left (текущим right). Та же проблема, что и при замене x и y значениях без использования переменной temp.

Ответ №1:

newTree = root означает, что если вы сейчас измените newTree.left , вы root.left также измените, у вас не будет фактического нового дерева, вы просто манипулируете одним деревом на месте. Если вы хотите это сделать, вы должны быть осторожны, чтобы не перезаписать материал, который вам понадобится позже. Если вы хотите поменять местами два числа, которые вы не можете записать a=b; b=a; , поскольку при втором назначении a они уже были бы изменены. Но вы делаете именно это с left помощью and right .
В принципе, вы должны написать:

 public void invertTree(TreeNode node) {
   if (node == null)
       return; 
    TreeNode tmp = node.left;
    node.left = node.right
    node.right = tmp;
    invertTree(node.left);
    invertTree(node.right);
}

В качестве альтернативы вы можете создать новое дерево, и тогда вам не нужно беспокоиться о tmp части, но вам понадобится довольно много new TreeNode операторов в нужных местах, тогда вы не должны использовать узел как в исходном, так и в новом дереве.

1. Ого. Да, это имеет большой смысл. У меня сложилось впечатление, что вы не могли бы сделать такую вещь с деревом. Большое вам спасибо! Это было исправлено, и решение работает.

Ответ №2:

Вот мое решение из leetcode. Это простая проблема рекурсии с обходом по порядку. Soln равно 0 (n), и он занимает 1% во время выполнения и 3% в памяти в исходном коде

 /**
 * 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;
 *     }
 * }
 */
 //recursion problem, swap every left with the right node in postorder 
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        if(root.left == null amp;amp; root.right == null) {
            return root;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}