二叉树解题（二）

Leetcode 226._翻转二叉树

        // 方法一：遍历二叉树
        public TreeNode InvertTree(TreeNode root)
        {
            // 遍历二叉树，交换每个节点的子节点
            Traverse(root);
            return root;
        }
        // 二叉树遍历函数
        void Traverse(TreeNode root) {
            if (root == null) return;
            // 每一个节点需要做的事就是交换它的左右子节点
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            // 遍历框架，去遍历左右子树的节点
            Traverse(root.left);
            Traverse(root.right);
        }

        // 方法二：递归函数分解问题
        public TreeNode InvertTree(TreeNode root)
        {
            if (root == null) return root;
            // 翻转左右子树
            TreeNode left = InvertTree(root.left);
            TreeNode right = InvertTree(root.right);
            // 交换左右子节点
            root.left = right;
            root.right = left;
            // 以 root 为根的这棵二叉树已经被翻转，返回 root
            return root;
        }

Leetcode 116._填充每个节点的下一个右侧节点指针

        public Node Connect(Node root)
        {
            if (root == null) return null;
            Traverse(root.left,root.right);
            return root;
        }
        void Traverse(Node left,Node right)
        {
            if (left == null|| right == null) return;
            // 将传入的两个节点穿起来
            left.next = right;
            // 连接相同父节点的两个子节点
            Traverse(left.left,left.right);
            Traverse(right.left, right.right);
            // 连接跨越父节点的两个子节点
            Traverse(left.right, right.left);
        }

Leetcode 114._二叉树展开为链表

        public void Flatten(TreeNode root)
        {
            if (root == null) return;
            Traverse(root);
        }
        void Traverse(TreeNode root)
        {
            if (root == null) return;
            // 遍历拉平左右子树
            Traverse(root.left);
            Traverse(root.right);
            // 后序位置
            TreeNode left = root.left;
            TreeNode right = root.right;
            // 将左子树作为右子树
            root.left = null;
            root.right = left;
            // 将右子树添加到当前右子树末尾
            TreeNode p = root;
            while (p.right!=null)
            {
                p = p.right;
            }
            p.right = right;
        }