LeetCode226-Invert Binary Tree

题目

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

分析

这道题目是遍历二叉树的变体。递归遍历二叉树的题目不外乎需要注意三点:

  • 次序:选择哪种次序遍历,需要根据题意进行选择,本题显然应是后序遍历,因为根一定是要等到左、右子树已经交换完毕后,再最后总地去交换左、右两棵子树。
  • 出口:递归都需要出口,否则就是无限递归了。出口通常与传入的参数有关联,根据这个参数携带信息的不同,设置return语句。如本题就是当传入的子树root为空的时候(即已经是叶子节点的左或右子树了),那么一个空节点怎么可能还能交换它的左右子树呢,因而我们直接null作为本次子树交换结果,返回上层供给其父节点交换用。
  • 返回值:根据不同情况我们需要设置不同的返回值,但因为树是递归定义的,所以通常这个返回值与题目最后要解得的答案有关系,比如求树高那返回int、求树节点数返回int、求树中某路径返回list以及本题求镜像树自然是返回TreeNode。
  • 访问根:左右递归遍历子树得到的只是上一步的解,我们最终还是要利用上一步的解,让他们服务于我们当前步的问题,因此访问根部分就是原子操作,是需要根据题目具体实现逻辑的地方了。本题即是将前面递归得到的两个子树进行交换

上面基本已经有了该题的解题思路了:后序遍历这棵二叉树,从叶子节点开始逐步向上层交换左右子树。

代码

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        
        if(root == null) 
            return null;
        
        //获得左、右子树
        TreeNode leftTree = invertTree(root.left); //先左子树遍历
        TreeNode rightTree = invertTree(root.right); //后右子树遍历
        
        //交换(访问根)
        root.left = rightTree;
        root.right = leftTree;
        
        return root;
    }
}

Leave a Comment.