代码随想录算法训练营第十八天|513.找树左下角的值、112.路径总和、113.路径总和ii、106.从中序与后序遍历序列构造二叉树

513.找树左下角的值

public class Solution {
    public int FindBottomLeftValue(TreeNode root) {
        var cnt=0;
        var ans=0;
        var sum=0;
        var q=new Queue<TreeNode>();
        q.Enqueue(root);
        while(q.Count!=0)
        {
            var size=q.Count;
            cnt++;
            while(size!=0)
            {
                size--;
                var cur=q.Dequeue();
                if(cur.left!=null)
                {
                    q.Enqueue(cur.left);
                }
                if(cur.right!=null)
                {
                    q.Enqueue(cur.right);
                }
            }
        }
        var q1=new Queue<TreeNode>();
        q1.Enqueue(root);
        while(q1.Count!=0)
        {
            var size=q1.Count;
            sum++;
            while(size!=0)
            {
                size--;
                var cur=q1.Dequeue();
                if(sum==cnt)
                {
                ans=cur.val;
                break;
                }
                if(cur.left!=null)
                {
                    q1.Enqueue(cur.left);
                }
                if(cur.right!=null)
                {
                    q1.Enqueue(cur.right);
                }
            }
        }       
        return ans;
    }
    }

用一个层序遍历找到最底层，然后最底层第一个弹出的元素则是左下角那个元素。

112.路径总和

public class Solution {
    public bool HasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        if(root.left==null&&root.right==null&&targetSum==root.val) return true;
        return HasPathSum(root.left,targetSum-root.val)||HasPathSum(root.right,targetSum-root.val);
}
}

空节点直接返回False，结束条件另一个则是左节点和右节点为空，TargetSum刚好等于该节点值即成功了，如果不中，则继续递归左节点，目标值就需要减去当前节点值，然后同时去递归右节点也减去当前值，两个任意一个找到了都是True。

113.路径总和ii

public class Solution {
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        var ans=new List<IList<int>>();
        if(root==null)
        {
            return ans;
        }
        var an=new List<int>();
        A(root,targetSum,ans,an);
        return ans;
    }
    public void A(TreeNode node, int targetSum, List<IList<int>> ans, List<int> an)
    {
        an.Add(node.val);
        if(node.left==null&&node.right==null)
        {
            if(targetSum-node.val==0)
            {
                ans.Add(new List<int>(an));
            }
               return;
        }
        if(node.left!=null)
        {
            A(node.left,targetSum-node.val,ans,an);
            an.RemoveAt(an.Count-1);
        }
        if(node.right!=null)
        {
            A(node.right,targetSum-node.val,ans,an);
            an.RemoveAt(an.Count-1);
        }
    }
}

首先排除根为空节点，然后构造一个函数A用于实现功能。终止条件也是叶子结点和目标值刚好相等，这个时候将路径储存，否则就回溯去掉最后一个路径，然后当前节点的左右节点分别递归。

106.从中序与后序遍历序列构造二叉树

public class Solution {
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        if(inorder.Length==0||postorder.Length==0)
        {
            return null;
        }
        var rootV=postorder.Last();
        var root=new TreeNode(rootV);
        var index=Array.IndexOf(inorder,rootV);
        root.left=BuildTree(inorder.Take(index).ToArray(),postorder.Take(index).ToArray());
        root.right=BuildTree(inorder.Skip(index+1).ToArray(),postorder.Skip(index).Take(inorder.Length-index-1).ToArray());
        return root;
    }
}

代码不多但逻辑性很强，需要在后续数组最后一个找到根节点，然后在前序数组里面找到这个根节点记录Index将其左右隔开，然后前序的左前序则是Index左部分，index右部分则是后续的左后续，剩下的同理，然后递归结束返回根节点即可。