二叉树的左右子树交换 #141

Activity

1. sisterAn

   added

   LeetCode

   美团

   on Dec 22, 2020
2. liuzb30 commented on Dec 23, 2020

   

   liuzb30

   on Dec 23, 2020

   Last edited by sisterAn

   More actions

   var invertTree = function(root) {
       if(root==null) return root
       const queue = [root]
       while(queue.length){
           const cur = queue.shift();
           // 交换左右节点
           [cur.left,cur.right] = [cur.right,cur.left]
           cur.left && (queue.push(cur.left))
           cur.right && (queue.push(cur.right))
       }
       return root
   }
3. sisterAn commented on Dec 23, 2020

   

   sisterAn

   on Dec 23, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   遍历+交换左右子树

   解题思路： 从根节点开始依次遍历每个节点，然后交换左右子树既可

   const invertTree = (root) => {
       if(!root) return null
       // 先翻转当前节点的左右子树
       const temp = root.left
       root.left = root.right
       root.right = temp
       // 然后遍历左子树
       invertTree(root.left)
       // 再遍历右子树
       invertTree(root.right)
       return root
   }

   这里采用的是前序遍历，也可以是后序遍历或层序遍历