二叉树解题（一）

先理解二叉树的前中后序遍历：

前序遍历=左子树前序遍历+右子树前序遍历

所以中序和后序只要将res.Add(root.val);放到对应位置;

        public IList<int> Traversal(TreeNode root){
            List<int> res = new List<int>();
            if (root == null)
                return res;
            // 前序位置 res.Add(root.val);
            left = Traversal(root.left);
            // 中序位置 res.Add(root.val);
            right = Traversal(root.right);
            // 后序位置 res.Add(root.val);
            return res;
        }

前序位置在代码进入节点时执行；

后序位置在代码离开节点时执行；

中序位置在代码遍历完左子树，开始遍历右子树前执行；

在这三个特殊的时间点可以做需要的事。

你只需要思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会对所有节点做相同的操作。

遇到一道二叉树的题目时的通用思考过程是：是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要设计到子树信息, 建议使用后续遍历

Leetcode 617.合并二叉树--简单

        public TreeNode MergeTrees(TreeNode root1, TreeNode root2)
        {
            // 一棵树没有，接上另一棵树有，
            if (root1 == null)
                return root2;
            if (root2 == null)
                return root1;
            // 合并相同位置的值
            root1.val +=root2.val;
            // 递归合并左右子树
            root1.left = MergeTrees(root1.left, root2.left);
            root1.right = MergeTrees(root1.right, root2.right);

            return root1;
        }

Leetcode 669.修剪二叉搜索树--中等

        public TreeNode TrimBST(TreeNode root, int low, int high) {
            if (root==null) return null;
            // 删除左边(root和root.left)所有节点,返回root.right
            if (root.val<low)
            {
                return TrimBST(root.right, low, high);
            }
            // 删除右边(root和root.right)所有节点,返回root.left
            if (root.val > high)
            {
                return TrimBST(root.left, low, high);
            }
            // 在[low,hight]区间中不做处理
            root.left = TrimBST(root.left, low, high);
            root.right = TrimBST(root.right, low, high);
            return root;
        }

Leetcode 124.二叉树中的最大路径和--困难

        int res = int.MinValue;
        public int MaxPathSum(TreeNode root)
        {
            if (root == null) return 0;
            Traverse(root);
            return res;
        }
        int Traverse(TreeNode root)
        {
            if (root == null) return 0;
            int left = Math.Max(0, Traverse(root.left));
            int right = Math.Max(0, Traverse(root.right));
            // 后序位置,更新最大路径和
            res = Math.Max(res, root.val + left + right);
            // 从根节点root为起点的最大单边路径和
            return Math.Max(left,right)+root.val;
        }