美文网首页TREE
226. Invert Binary Tree

226. Invert Binary Tree

作者: DrunkPian0 | 来源:发表于2017-07-12 00:57 被阅读20次

    翻转二叉树。Google的热身题。会写翻转二叉树你就比Max Howell强了。。

    我的递归DFS代码:

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

    另一种递归DFS代码:

    public class Solution {
        public TreeNode invertTree(TreeNode root) {
            
            if (root == null) {
                return null;
            }
    
            final TreeNode left = root.left,
                    right = root.right;
            root.left = invertTree(right);
            root.right = invertTree(left);
            return root;
        }
    }
    

    另外这题用Stack和Queue都能解。
    用Queue就是BFS。
    Stack就是DFS! Stack执行过程跟递归DFS一样(DFS本身就是一层层的,神奇)。
    详见:
    https://leetcode.com/problems/invert-binary-tree/#/solutions

    相关文章

      网友评论

        本文标题:226. Invert Binary Tree

        本文链接:https://www.haomeiwen.com/subject/fjyvhxtx.html