[LeetCode]--226. Invert Binary Tree

简介: Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9to 4 / \ 7 2 / \ / \ 9 6 3 1Trivia: This problem was inspired by this original twe

Invert a binary tree.

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

to

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

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

这个题很容易想到递归求解左右子树,不多说,上代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

LeetCode官方链接

目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
40 1
Leetcode Minimum Depth of Binary Tree (面试题推荐)
计算树的最小深度 很简单的一道题,只需要遍历一次树,到叶子节点的时候计算一下深度和当前最小深度比较,保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练,求更精简的方法。
44 0
Leetcode Binary Tree Postorder Traversal(面试题推荐)
非递后续归遍历二叉树,肯定得用到栈。先序遍历很好写,但后续遍历就不是那么容易了。 只需要设置个指针pre,指向最后输出的那个节点就行了,只要判断cur指针指向的是上次输出节点的父节点,且cur无其他未遍历的节点,这个时候就把cur节点输出即可,然后更改pre。原理是要遍历当前节点,其所有子节点都必须遍历完,因为肯定是先左后右,所以只需一个指针保持前一次输出的结果即可。
50 0
Leetcode 236. Lowest Common Ancestor of a Binary Tree
根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。
36 0
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
45 0
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode 429. N-ary Tree Level Order Traversal
给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
84 0
LeetCode 429. N-ary Tree Level Order Traversal
|
Python
LeetCode 401. Binary Watch
二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。 每个 LED 代表一个 0 或 1,最低位在右侧。
102 0
LeetCode 401. Binary Watch
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree