二叉樹解題（二）

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;
        }