Binary tree problem solving (1)

First understand the traversal of the first, middle and second order of binary tree ：

The former sequence traversal = Left subtree preorder traversal + Right subtree preorder traversal

Therefore, the middle sequence and the rear sequence only need to res.Add(root.val); Put it in the corresponding position ;

        public IList<int> Traversal(TreeNode root){
            List<int> res = new List<int>();
            if (root == null)
                return res;
            //  Preamble position  res.Add(root.val);
            left = Traversal(root.left);
            //  Middle order position  res.Add(root.val);
            right = Traversal(root.right);
            //  Post sequence position  res.Add(root.val);
            return res;
        }

The preamble position is executed when the code enters the node ;

The post sequence position is executed when the code leaves the node ;

The middle order position is after the code traverses the left subtree , Execute before traversing the right subtree ;

You can do what you need at these three special time points .

You just need to think about what each node should do , Don't worry about the others , Throw it to the binary tree traversal framework , Recursion will do the same for all nodes .

The general thinking process when encountering the problem of a binary tree is ： Whether you can get the answer by traversing the binary tree ？ If not , Whether a recursive function can be defined , Pass the subproblem （ subtree ） The answer to the original question ? If you need to design subtree information , Follow up traversal is recommended

Leetcode 617. Merge binary tree -- Simple

        public TreeNode MergeTrees(TreeNode root1, TreeNode root2)
        {
            //  No tree , Next to another tree ,
            if (root1 == null)
                return root2;
            if (root2 == null)
                return root1;
            //  Merge values at the same location 
            root1.val +=root2.val;
            //  Recursively merge left and right subtrees 
            root1.left = MergeTrees(root1.left, root2.left);
            root1.right = MergeTrees(root1.right, root2.right);

            return root1;
        }

Leetcode 669. Prune the binary search tree -- secondary

        public TreeNode TrimBST(TreeNode root, int low, int high) {
            if (root==null) return null;
            //  Delete left (root and root.left) All nodes , return root.right
            if (root.val<low)
            {
                return TrimBST(root.right, low, high);
            }
            //  Delete the right side (root and root.right) All nodes , return root.left
            if (root.val > high)
            {
                return TrimBST(root.left, low, high);
            }
            //  stay [low,hight] No processing in the interval 
            root.left = TrimBST(root.left, low, high);
            root.right = TrimBST(root.right, low, high);
            return root;
        }

Leetcode 124. The maximum path in a binary tree and -- difficult

        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));
            //  Post sequence position , Update the maximum path and 
            res = Math.Max(res, root.val + left + right);
            //  From the root node root Is the maximum unilateral path and 
            return Math.Max(left,right)+root.val;
        }